题目

计算逻辑表达式，只包含与和或，只包含0和1，根据中缀表达式输出计算结果，短路与的次数，短路或的次数。

// 开一个优先级单调递增的栈维护运算符，再开一个栈记录遇到的01数值
// 弹出运算符从01的栈中取出两个数构成当前运算符的左右子树
// 然后把当前运算符连同其字数作为一个新的数压入数值栈
// 规则如下 
// 1.运算符栈优先级单调递增。
// 2.遇到左括号直接当成新的栈，相当于开了一个新的递增的栈
// 3.相同的也不行，两个或就要把后面的或先算掉，算完之后把结果再放数值栈。
// 4.遇到右括号就要一直出栈，直到遇到左括号
// 5.如果算完了，就要把栈清空

// 如何统计短路次数
// 对建立好的二叉树进行遍历：
// 1.如果左子树的结果为1，且当前节点的运算符为"|",则跳过右子树，并记录一次短路
// 2.如果左子树的结果为0，且当前节点的运算符为"&",则跳过右子树，并记录一次短路
#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;
struct node {
    char ch;
    int l, r;
    // 这里的l,r指的是再a中的下标，而不是节点
    node(char ch1 = 0, int l1 = 0, int r1 = 0) : ch(ch1), l(l1), r(r1) {}
} a[N];

int tot = 0, cnt0 = 0, cnt1 = 0;
// tot 实际上是一个索引，指向数组中最新的节点。
// 最后合并的节点是整个二叉树的根节点，所以我们可以通过dfs根节点遍历整棵树 
// 内联函数，加快节点获取
inline int getnode(char ch, int l, int r) {
    a[++tot] = node(ch, l, r);
    return tot; // 注意这里返回的是下标
}

int dfs(int x){
    // 如果抵达了左右叶子结点,返回当前节点的数值 
    if(a[x].l == 0) return a[x].ch - '0';
    // 先遍历左子树 
    int lv = dfs(a[x].l);
    // 如果左子节点是0，当前节点是&,与短路加一 ,跳过右子树 
    if(lv == 0 && a[x].ch == '&'){
        cnt0++; 
        return 0;
    }
    //如果左子节点是1，当前节点是|,或短路加一 ,跳过右子树
    if(lv == 1 && a[x].ch == '|'){
        cnt1++; 
        return 1;
    }
    //否则继续遍历右子树
    int rv = dfs(a[x].r);
    //并进行计算，如果是与则作与运算，否则做或运算 
    return a[x].ch == '&' ? lv & rv : lv | rv;
}
int main() {
    int tp = 0, top = -1, n;
    char c[N], q[N];
    int v[N];
    // 从1开始读入进去
    scanf("%s", c + 1);
    n = strlen(c + 1);
    // 这里先将第一个位置放置左括号，再将最后一个位置放置右括号
    c[0] = '(';
    c[n + 1] = ')';
    n += 2;
    // 分为以下几种情况，由于我们要维护一个递增的字符栈(同时当遇到括号的时候，可以重新开始递增)
    // 1.数字进入数值栈
    // 2.当前是&或者是|
    // 1)当前栈顶元素和当前元素都是& 2)栈顶和当前元素都是| 3)栈顶是最高优先级的&,而当前元素是|
    // 此时我们将栈顶元素pop出来，然后将两个数字从数值栈pop出来，构建新的节点并压入数值栈
    // 3.如果是左括号直接入栈
    // 4.如果是右括号，就要找到左括号为止，将内部的所有元素都pop出来，形成新的子树，最后再弹出左括号
    for (int i = 0; i < n; i++) {
        if (c[i] == '0' || c[i] == '1') {
            v[++tp] = getnode(c[i], 0, 0); // 入栈数字
        } else if (c[i] == '&' || c[i] == '|') {
            while (top >= 0 && ((c[i] == '&' && q[top] == '&') || (c[i] == '|' && (q[top] == '|' || q[top] == '&')))) {
                int r = v[tp--]; // 右子树
                int l = v[tp--]; // 左子树
                v[++tp] = getnode(q[top--], l, r); // 构建节点
            }
            q[++top] = c[i]; // 入栈运算符
        } else if (c[i] == '(') {
            q[++top] = c[i]; // 入栈左括号
        } else if (c[i] == ')') {
            while (top >= 0 && q[top] != '(') {
                int r = v[tp--]; // 右子树
                int l = v[tp--]; // 左子树
                v[++tp] = getnode(q[top--], l, r); // 构建节点
            }
            top--; // 弹出左括号
        }
    }

    printf("%d\n", dfs(tot)); // 输出计算结果
    printf("%d %d\n", cnt0, cnt1); // 输出短路计数
    return 0;
}

参考文献

哔哩哔哩 2022CSP-JS复赛普及组真题讲解 视频号:BV1je411Y7Ck

eg:上面的代码洛谷没过，dfs应该要用栈实现才能过，还是看acwing题解,下面的过了。用三个栈来记录，并用一个栈来实现递归的计算短路与和短路或的个数。

#include <bits/stdc++.h>

using namespace std;

// 获取优先级函数
int get (char ch) {
    if (ch == '&') return 2;
    if (ch == '|') return 1;
    if (ch == '(') return 0;
}
// 定义三个栈
stack<int> stk; // 数字栈
stack< pair<int, int> > c; // 短路与与短路或的次数，用递归栈实现计算
stack<char> op; //操作符栈
pair<int, int> m1, m2;
void calc () {
    int n1 = stk.top (); stk.pop ();
    m1 = c.top (); c.pop ();
    int n2 = stk.top (); stk.pop ();
    m2 = c.top (); c.pop ();
    char opt = op.top (); op.pop ();
    if (opt == '&') {
        // stk用来计算总结果,c用来计算短路次数
        stk.push (n1 & n2);
        if (! n2) {
            // 用栈实现递归计算短路与和短路或的次数
            c.push ({m2.first + 1, m2.second});
        } else {
            c.push ({m1.first + m2.first, m1.second + m2.second});
        }
    } else if (opt == '|') {
        stk.push (n1 | n2);
        if (n2 == 1) {
            c.push ({m2.first, m2.second + 1});
        } else {
            c.push ({m1.first + m2.first, m1.second + m2.second});
        }
    }
}
int main () {
    string s; cin >> s;
    int tmp;
    for (int i = 0; i < s.size (); i ++ ) {
        if (s[i] >= '0' && s[i] <= '1')  {
            tmp = s[i] - '0';
            stk.push (tmp);
            c.push ({0, 0});
        } else {
            if (s[i] == '(') {
                op.push (s[i]);
            } else if (s[i] == ')') {
                while (op.top () != '(') calc ();
                op.pop ();
            } else {
                // 如果操作符栈不为空，且当前运算级比栈顶元素运算及高，就弹出栈顶元素
                while (op.size () && get (op.top ()) >= get (s[i])) {
                    calc ();
                } 
                op.push (s[i]);
            }
        }
    }
    while (op.size ()) calc ();
    cout << stk.top () << '\n' << c.top ().first << ' ' << c.top ().second;
    return 0;
}