Solution for facebook qualification round 2019, Problem 3

fb_qual_2019_3.cpp

// Given bollean expression with only one variable (x, note that X := !x),
// find the minimum number of symbols editing to make it independent on the variable
// value. For example, (x&0) does not depend on x.
//
// The idea is that we can always achieve this by changing the root operation in AST
// So we just find out if the output of the expression (represented as vector 0xAB, where A,B <- {0,1})
// is either 0x11 or 0x00.
// Otherwise, there is exactly one modification to achieve what is needed (change root operation).
#include <bits/stdc++.h>
using namespace std;

char eval(char v1, char v2, char op) {
    int a = v1 - '0';
    int b = v2 - '0';
    if (op == '^') return char(a^b) + '0';
    if (op == '&') return char(a&b) + '0';
    //if (op == '|') 
    return char(a|b) + '0';
}

char compute(string& s) {
    char v1 = '0', v2 = '0', op = '-';
    stack<char> st;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == ')') {
            v1 = st.top();
            st.pop();
            op = st.top();
            st.pop();
            if (op == '(')
                st.push(v1);
            else {
                v2 = st.top();
                st.pop();
                assert(st.top() == '(');
                st.pop();
                st.push( eval(v1, v2, op) );
            }
        } else if (s[i] == 'x') {
            st.push('1');
        } else if (s[i] == 'X') {
            st.push('2');
        } else if (s[i] == '0') {
            st.push('0');
        } else if (s[i] == '1') {
            st.push('3');
        } else // operator
            st.push(s[i]);
    }
    return st.top();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int T;
    cin >> T;
    for (int t = 0; t < T; ++t) {
        string expr;
        cin >> expr;
        cout << "Case #" << t + 1 << ": ";
        char res = compute(expr);
        if (res == '3' || res == '0')
            cout << "0" << endl;
        else
            cout << "1" << endl;
    }
    return 0;
}