Expert.
Put your skills to the test.

Problem summary

Evaluate a parenthesized expression under multiple Boolean assignments. Adjacent expressions are combined by NAND: the result is zero only when both arguments are one. Without parentheses operations associate from left to right. Variables are precisely the first k lowercase letters.

Constraints

Expression length ≤ 1000; at least 1 and at most 200000 assignments; at most 26 variables.

Worked example

Official sample; other valid outputs may exist.

a(a)(ab(ca)bb)c
011
100
010
111
001
2

01101

Solution analysis

1. Parse the expression once into postfix instructions. Each parenthesis level contains a left-to-right chain: after parsing an atom, emit NAND after every following atom. Parenthesized atoms recursively emit their own instructions.
2. For each assignment execute the postfix program with a Boolean stack. A variable pushes its assigned bit. NAND pops two bits and pushes the negation of their conjunction. This avoids reparsing for every query.
3. For an unparenthesized abc, postfix is ab#c#, where # means NAND. With a=b=c=1, the first NAND gives 0 and the second gives 1; this differs from right association.

Why it works

Structural induction proves that parsing each atom emits its value, and the chain parser emits the specified left fold. Standard stack evaluation computes each emitted operation on the two corresponding subexpression values. Thus every reported bit equals the defined expression value.

Watch out. NAND is not associative. Parentheses around one variable do not add an operation.

An independently written complete program with standard headers.

// Key idea: Structural induction proves that parsing each atom emits its value, and the chain parser
// emits the specified left fold. Standard stack evaluation computes each emitted operation on the two
// corresponding subexpression values.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string expression,program;
size_t position=0;
void parseChain();
void parseAtom(){
    if(expression[position]=='('){
        ++position;
        parseChain();
        ++position;
    }
    else{
        program+=expression[position++];
    }
}
void parseChain(){
    parseAtom();
    while(position<expression.size()&&expression[position]!=')'){
        parseAtom();
        program+='#';
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>expression;
    parseChain();
    string assignment;
    vector<int>stack(program.size());
    while(cin>>assignment&&assignment!="2"){
        int size=0;
        for(char instruction:program){
            if(instruction!='#'){
                stack[size++]=assignment[instruction-'a']-'0';
            }
            else{
                int right=stack[--size];
                stack[size-1]=!(stack[size-1]&&right);
            }
        }
        cout<<stack[0];
    }
    cout<<'\n';
}