建树并从上往下递归计算

#include <iostream>
#include <unordered_map>
#include <stack>
using namespace std;

const int N = 1e6+10;
unordered_map<char, int> mp = {{'(', 0}, {'|', 1}, {'&', 2}};
stack<int> num;
stack<char> op;
int l[N], r[N];
char w[N];
int idx, ands, ors;

void oval(){
    int b = num.top();
    num.pop();
    int a = num.top();
    num.pop();
    char x = op.top();
    op.pop();
    w[++idx] = x;
    l[idx] = a;
    r[idx] = b;
    num.push(idx);
}
int dfs(int u){
    if(w[u] == '0' || w[u] == '1') return w[u] - '0';
    if(w[u] == '&'){
        if(!dfs(l[u])){
            ands++;
            return 0;
        }else{
            return dfs(r[u]);
        }
    }else if(w[u] == '|'){
        if(dfs(l[u])){
            ors++;
            return 1;
        }else{
            return dfs(r[u]);
        }
    }
}

int main(){
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ ){
        char t = str[i];
        if(isdigit(t)){
            w[++idx] = t;
            num.push(idx);
        }else if(t == '(') op.push(t);
        else if (t == ')'){
            while (op.top() != '(') oval();
            op.pop();
        }else{
            while (op.size() && mp[t] <= mp[op.top()]) oval();
            op.push(t);
        }
    }
    while(op.size()) oval();
    cout << dfs(idx) << endl;
    cout << ands << ' ' << ors;
    return 0;
}