#include <iostream>
#include <stack>
#include <string>
#include <fstream>

using namespace std;

struct node
{
    string payload;
    bool is_operator;
    bool value;
    struct node *left;
    struct node *right;
};

struct node *newnode(string payload, bool isop, bool value, node *lr, node *rc);
string infix2postfix(string data);
int get_prec(string n);
stack<struct node *> build_expr_tree(string infix);
void inorder(struct node *cr);
bool eval(struct node *cr);
struct node *change_state(struct node *cr, string key);

int main()
{
    ifstream inp("bool.in");
    ofstream out("bool.out");
    if(inp.is_open() && out.is_open())
    {
        string s;
        getline(inp, s);
        node *st = build_expr_tree(infix2postfix(s)).top();
        cout << infix2postfix(s) << "\n";
        int n;
        inp >> n;
        for(int i = 0; i < n; i++)
        {
            char c;
            inp >> c;
            string k(1, c);
            st = change_state(st, k);
            out << eval(st);
        }
        inorder(st);
        if(!n)
        {
            out << eval(st);
        }

        inp.close();
        out.close();
    }
    else
    {
        cout << "Error\n";
    }

    return 0;
}

struct node *change_state(struct node *cr, string key)
{
    if(cr != NULL)
    {
        if(!cr->is_operator)
        {
            if(cr->payload == key)
            {
                cout << "before " << cr->payload << ": " << cr->value << "\n";
                cr->value = !cr->value;
                cout << "after " << cr->payload << ": " << cr->value << "\n";
            }
            return cr;
        }
        else
        {
            cr->left = change_state(cr->left, key);
            cr->right = change_state(cr->right, key);
            return cr;
        }
    }
    else
    {
        return NULL;
    }
}

bool eval(struct node *cr)
{
    if(cr != NULL)
    {
        if(!cr->is_operator)
        {
            return cr->value;
        }
        else
        {
            if(cr->payload == "NOT")
            {
                return !eval(cr->left);
            }
            else if(cr->payload == "AND")
            {
                return eval(cr->left) && eval(cr->right);
            }
            else if(cr->payload == "OR")
            {
                return eval(cr->left) || eval(cr->right);
            }
        }
    }
}

void inorder(struct node *cr)
{
    if(cr != NULL)
    {
        inorder(cr->left);
        cout << cr->payload << "(" << cr->value << ") ";
        inorder(cr->right);
    }
}

stack<struct node *> build_expr_tree(string infix)
{
    stack<struct node *> st;
    string current = "";
    for(int i = 0; i < infix.size(); i++)
    {
        if(infix[i] == ' ')
        {
            if(current.size() == 1)
            {
                st.push(newnode(current, false, false, NULL, NULL));
            }
            else
            {
                if(current == "NOT")
                {
                    struct node *t = st.top();
                    st.pop();
                    st.push(newnode(current, true, false, t, NULL));
                }
                else if(current == "TRUE")
                {
                    st.push(newnode(current, false, true, NULL, NULL));
                }
                else if(current == "FALSE")
                {
                    st.push(newnode(current, false, false, NULL, NULL));
                }
                else
                {
                    struct node *t1 = st.top();
                    st.pop();
                    struct node *t2 = st.top();
                    st.pop();
                    st.push(newnode(current, true, false, t2, t1));
                }
            }
            current.clear();
        }
        else
        {
            current += infix[i];
        }
    }
    return st;
}

int get_prec(string n)
{
    if(n == "OR")
    {
        return 1;
    }
    else if(n == "AND")
    {
        return 2;
    }
    else if(n == "NOT")
    {
        return 3;
    }
    else
    {
        return -1;
    }
}

string infix2postfix(string data)
{
    string infix = "";
    stack<string> st;
    string current = "";
    for(int i = 0; i < data.size(); i++)
    {
        if(data[i] == ' ')
        {
            if(current.size())
            {
                if(current.size() == 1)
                {
                    infix += current + " ";
                }
                else if(current == "TRUE")
                {
                    infix += "TRUE ";
                }
                else if(current == "FALSE")
                {
                    infix += "FALSE ";
                }
                else
                {
                    while(!st.empty() && get_prec(current) <= get_prec(st.top()))
                    {
                        infix += st.top();
                        st.pop();
                    }
                    st.push(current + " ");
                }
                current.clear();
            }
        }
        else if(data[i] == '(')
        {
            if(current.size())
            {
                if(current.size() == 1)
                {
                    infix += current + " ";
                }
                else if(current == "TRUE")
                {
                    infix += "TRUE ";
                }
                else if(current == "FALSE")
                {
                    infix += "FALSE ";
                }
                else
                {
                    while(!st.empty() && get_prec(current) <= get_prec(st.top()))
                    {
                        infix += st.top();
                        st.pop();
                    }
                    st.push(current + " ");
                }
                current.clear();
            }

            string s = "(";
            st.push(s);
        }
        else if(data[i] == ')')
        {
            if(current.size())
            {
                if(current.size() == 1)
                {
                    infix += current + " ";
                }
                else if(current == "TRUE")
                {
                    infix += "TRUE ";
                }
                else if(current == "FALSE")
                {
                    infix += "FALSE ";
                }
                else
                {
                    while(!st.empty() && get_prec(current) <= get_prec(st.top()))
                    {
                        infix += st.top();
                        st.pop();
                    }
                    st.push(current);
                }
                current.clear();
            }
            while(!st.empty() && st.top() != "(")
            {
                infix += st.top();
                st.pop();
            }
            st.pop();
        }
        else
        {
            current += data[i];
        }
    }
    if(current.size())
    {
        infix += current + " ";
    }
    while(!st.empty())
    {
        infix += st.top();
        st.pop();
    }
    return infix;
}

struct node *newnode(string payload, bool isop, bool value, node *lr, node *rc)
{
    struct node *kp = new struct node;
    kp->payload = payload;
    kp->is_operator = isop;
    kp->value = value;
    kp->left = lr;
    kp->right = rc;

    return kp;
};