python/TangDou/CSP-J/J2-2022/expr_Final.cpp

/*
测试用例1：
0&(1|0)|(1|1|1&0)
答案：
1
1 2

测试用例2：
(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0
答案：
0
2 3
*/
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int v, a, b; // v:代表当前的结果值，a: &短路的次数 b:|短路的次数
};

stack<Node> num;
stack<char> stk;

unordered_map<char, int> h{{'|', 1}, {'&', 2}};

void eval() {
    // 这里要注意从栈中弹出元素的顺序，先出来的是y,后出来的是x
    Node y = num.top();
    num.pop();

    Node x = num.top();
    num.pop();

    char p = stk.top();
    stk.pop();

    Node r;
    if (p == '|') {
        if (x.v == 1)
            r = {1, x.a, x.b + 1};
        else
            r = {y.v, x.a + y.a, x.b + y.b};
    } else if (p == '&') {
        if (x.v == 1)
            r = {y.v, x.a + y.a, x.b + y.b};
        else
            r = {0, x.a + 1, x.b};
    }
    num.push(r);
}

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {
            int x = 0;
            while (i < s.size() && isdigit(s[i])) {
                x = x * 10 + s[i] - '0';
                i++;
            }
            i--;
            num.push({x, 0, 0});
        } else if (s[i] == '(')
            stk.push(s[i]);
        else if (s[i] == ')') {
            while (stk.top() != '(') eval();
            stk.pop();
        } else {
            while (stk.size() && h[stk.top()] >= h[s[i]]) eval();
            stk.push(s[i]);
        }
    }
    while (stk.size()) eval();

    printf("%d\n", num.top().v);
    printf("%d %d\n", num.top().a, num.top().b);
    return 0;
}