表达式树的建立和遍历

启发：2022CSPJ T3
表达式树是一棵二叉树，二叉树的遍历分为：
1.前序遍历（中左右）
2.中序遍历（左中右）
3.后序遍历（左右中）
中序遍历得到的表达式是人看的，前序和后序得到的方便机器运算，其中后序遍历方便在线性时间内求解，并且运算顺序唯一确定。
对于一棵表达式树，其叶节点一定是数字，其他节点一定是运算符。
若要建立一棵表达式树，那么一定需要知道中序遍历的结果，以及先序遍历和后序遍历其中之一。

中序遍历转化为后序遍历

对于一个表达式，如 $ a + b \times c + d \times (e+f) $， 其表达的是中序遍历的结果，当需要转化为后续遍历时，我们需要建立一个运算符栈，步骤如下：
1.当遇到数字时，直接将其添加到后序遍历表达式的最后
2.当遇到 $ ( $ 时，将左括号压入运算符栈
3.当遇到 $ ) $ 时，不断输出栈顶元素，直到遇到左括号，左括号出栈
4.当遇到其他运算符时，不断输出栈顶元素，保证输出的栈顶元素运算优先级大于等于该运算符，并将新运算符入栈
5.最后将运算符栈中剩余的元素依次输出

根据后序遍历求值

遍历后序遍历序列，并建立一个数字栈
1.当遇到数字时，将该数字压入栈
2.当遇到运算符时，取出栈顶的两个数字，运算后重新压入栈
最后栈顶元素即为表达式的值

表达式树的建立

这里以后序遍历和中序遍历建立表达式树（满二叉树）为例：
注意到中序遍历为“左中右”，后序遍历为“左右中”，也就是说表达式树的根节点一定是后序遍历的最后一个节点。
后序遍历中，对于一个节点，若其不是根节点，那么他前面的节点一定是该节点的右儿子，右儿子对应序列的前一个节点一定是左儿子。
也就是说，我们可以从后序遍历的最后一个节点开始建立表达式树，每次以当前的最后一个节点为根节点，将中序遍历序列划分为左右子树，然后再根据该节点在后序遍历中的前一个节点，先递归建立右子树（因为与根节点相邻的一定是右子树中的节点），再递归建立左子树即可。
\(eg.\)
对于中序遍历 $ DBEAGCF $ 和后序遍历 $ DEBGFCA $，由后序遍历序列可知，根节点为 \(A\)，所以可以将中序遍历划分为 $ DBE $ 和 $ GCF$ 。
\(A\) 前面一个节点为 \(C\)，所以其右儿子的根节点为 $ C $ ，右儿子的中序遍历被划分为 \(G\), \(C\), \(F\) ，当某些节点被单独划出来时，说明其是叶子节点，直接建立节点即可。
对于左儿子处理方式完全相同。

CSPJ2022 T3

给定了中序遍历结果，我们先将其转化为后序遍历，然后建立表达式树。
对于该题中的短路操作，我们可以理解为：
1.对于一个 \(&\) 运算符，检查其左儿子的运算结果是否为 $ 0 $ ，若为 $ 0 $ 即为一次短路，同时可以忽略右子树的计算
2.对于一个 \(|\) 运算符，检查其左儿子的运算结果是否为 $ 1 $ ，若为 $ 1 $ 即为一次短路，同时可以忽略右子树的计算
最后输出结果即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
const int MAXN = (int)1e6 + 10;
char mid[MAXN], bac[MAXN];
char val[MAXN];
int n, m, res1, res2, ans, cnt;
struct node{
    node *left, *right;
    int val = -1, cal = -1;
} *ROOT;
struct STACK{ char tag; int pos; };
std::unordered_map<int, int> hash;
template <class I> inline void read(I &x){
    x = 0; int f = 1; char ch;
    do { ch = getchar(); if(ch == '-') f = -1; } while(ch < '0' || ch > '9');
    do { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } while(ch >= '0' && ch <= '9');
    x *= f; return;
}
void transform(void){
    STACK stk[MAXN];
    int top = 0, tot = 0;
    for(int i = 1; i <= n; ++i){
        if(mid[i] == '(') stk[++top].tag = mid[i];
        else if(mid[i] == ')'){
            while(top && stk[top].tag != '('){
                bac[++m] = stk[top].tag;
                hash[m] = stk[top].pos;
                --top;
            }
            --top;
        }
        else if(mid[i] == '&'){
            ++tot;
            while(top && stk[top].tag != '(' && stk[top].tag == '&'){
                bac[++m] = stk[top].tag;
                hash[m] = stk[top].pos;
                --top;
            }
            stk[++top].tag = mid[i];
            stk[top].pos = tot;
        }
        else if(mid[i] == '|'){
            ++tot;
            while(top && stk[top].tag != '('){
                bac[++m] = stk[top].tag;
                hash[m] = stk[top].pos;
                --top;
            }
            stk[++top].tag = mid[i];
            stk[top].pos = tot;
        } else {
            ++tot;
            bac[++m] = mid[i];
            hash[m] = tot;
        }
    }
    while(top){
        bac[++m] = stk[top].tag;
        hash[m] = stk[top].pos;
        --top;
    }
    return;
}
node* build(int &k, int l, int r){
    if(l > r) return NULL;
    if(l == r){
        --k;
        node* tmp = new node;
        tmp->val = mid[l] ^ 48;
        tmp->left = tmp->right = NULL;
        return tmp;
    }
    int rt = k--;
    int p = hash[rt];
    node* tmp = new node;
    tmp->left = tmp->right = NULL;
    if(bac[rt] == '&') tmp->cal = 2;
    if(bac[rt] == '|') tmp->cal = 1;
    tmp->right = build(k, p + 1, r);
    tmp->left = build(k, l, p - 1);
    return tmp;
}
void DFS(node* k){
    if(k->val != -1) return;
    if(k->cal == 1){
        if(k->left->val == -1 && k->left != NULL) DFS(k->left);
        if(k->left->val == 1 && k->left != NULL){
            ++res2;
            k->val = 1;
            return;
        }
        if(k->left->val == 0 && k->left != NULL && k->right != NULL) DFS(k->right);
        k->val = k->left->val | k->right->val;
    }
    if(k->cal == 2){
        if(k->left->val == -1 && k->left != NULL) DFS(k->left);
        if(k->left->val == 0 && k->left != NULL){
            ++res1;
            k->val = 0;
            return;
        }
        if(k->left->val == 1 && k->left != NULL && k->right != NULL) DFS(k->right);
        k->val = k->left->val & k->right->val;
    }
    return;
}
int main(){
    // freopen("in.in", "r", stdin);
    scanf("%s", mid + 1);
    n = strlen(mid + 1);
    transform();
    for(int i = 1; i <= n; ++i) val[i] = mid[i];
    for(int i = 1, j = 0; i <= n; ++i){
        if(val[i] == '(' || val[i] == ')') continue;
        mid[++j] = val[i];
    }
    ROOT = build(m, 1, m);
    DFS(ROOT);
    ans = ROOT->val;
    printf("%d\n%d %d\n", ans, res1, res2);
    return 0;
}