yukicoder : No.1196 A lazy student

★どのぐらいが妥当なんだろうな。
https://yukicoder.me/problems/no/1196

問題

YES・NO・and・or・開き括弧・閉じ括弧・randomの7トークンで構成された数式が与えられる。
また、パラメータP,Q,Rが与えられる。
この数式はYES・NOのいずれかの値を取り、それぞれ以下のように計算される。

• x and yはx,yがともにYESならYES、それ以外NO
• x or yはx,yがともにNOならNO、それ以外YES
• ただし、and・orは演算後確率Rで結果が反転する
• randm(xy)はx,yがともにYESなら確率PでYES、そうでない場合確率QでYES
• and・or・括弧は一般的な数式と同じ演算子の優先順を持つ。

最終的に式がYESと評価される確率を求めよ。

解法

結局部分式においてYESとなる確率を考え、愚直に計算していけばよい。
構文解析が面倒だが、それ以上の難しさはないはず。

int N;
double P,Q,R;
string S,T;
char* C;


double expression();

double exp2() {
	if(*C=='Y') {
		C++;
		return 1;
	}
	if(*C=='N') {
		C++;
		return 0;
	}
	if(*C=='(') {
		C++;
		double A=expression();
		C++;
		return A;
	}
	
	C++;
	double A=expression();
	double B=expression();
	C++;
	return A*B*P+(1-A)*(1-B)*Q;
}

double exp1() {
	double A=exp2();
	while(*C=='A') {
		C++;
		double B=exp1();
		A=A*B;
		A=R*A+(1-R)*(1-A);
	}
	return A;
}
double expression() {
	double A=exp1();
	while(*C=='O') {
		C++;
		double B=exp1();
		A=1-(1-A)*(1-B);
		A=R*A+(1-R)*(1-A);
	}
	return A;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>P>>Q>>R;
	cin>>S;
	FOR(i,N) {
		if(S[i]=='Y') T+='Y';
		else if(S[i]=='N') T+='N';
		else if(S[i]=='(') T+="(";
		else if(S[i]==')') T+=")";
		if(S[i]=='a') {
			T+='A';
			i+=2;
		}
		else if(S[i]=='o') {
			T+='O';
			i+=1;
		}
		else if(S[i]=='r') {
			T+='R';
			i+=6;
		}
	}
	C=&T[0];
	_P("%.12lf\n",floor(expression()*100));
	
}

まとめ

構文解析系って面倒で余り面白さを感じることないんだけど、面白い問題もあるんだろうか。