Mr. X [Facebook Hacker Cup 2019 Qualification Round C]

https://www.facebook.com/hackercup/problem/589264531559040/
提出

前提知識

• 構文解析

解説

https://codeforces.com/gym/102249/submission/55747916

とっても難しそうな問題に見えるので、エスパーしよう。
x=false, x=trueの時を評価して、どちらも同じ結果になれば答えは0。
そうでなければ、うまいことやって1回で揃えられるだろうとエスパーして1を返す。
　
そのため、この問題は構文解析をうまくやる問題になった。
再帰で評価していこう。

string S, T;
//---------------------------------------------------------------------------------------------------
int idx;
bool eval() {
	if (T[idx] == '(') {
		idx++;
		auto a = eval();
		
		char op = T[idx];
		idx++;

		auto b = eval();
		idx++;

		if (op == '&') return a & b;
		else if (op == '|') return a | b;
		else return a ^ b;
	}

	if (T[idx] == '0') {
		idx++;
		return false;
	}
	if (T[idx] == '1') {
		idx++;
		return true;
	}
}
//---------------------------------------------------------------------------------------------------
int solve() {
	cin >> S;
	S += "#";

	bool res[2];
	rep(i, 0, 2) {
		T = S;
		char a = to_string(i)[0];
		char b = to_string(1 - i)[0];
		fore(c, T) {
			if (c == 'x') c = a;
			if (c == 'X') c = b;
		}

		idx = 0;
		res[i] = eval();
	}

	if (res[0] == res[1]) return 0;
	return 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	int T; cin >> T;
	rep(t, 0, T) printf("Case #%d: %d\n", t + 1, solve());
}