逻辑表达式 (CSP-J 2022)

这是这次CSP-J难度最大的一题（放在了第三题，第四题反而简单）。表达式解析是CSP-J经常考的实现难度较高的题型，是比较复杂的模拟题。这类题一般两种情况，一是需要建立表达式树，二是可以直接一遍扫描完成，用栈、状态变量和递归来辅助。比较友好的是，这道题是可以一遍扫描完成的。

两级优先级的运算，再加括号的表达式expr，基本可以看成三层：

| 优先级最低
& 优先级第二
数字，或者括号内的表达式(expr)，优先级最高

我们希望解析的时候只往前看一个字符，这样程序最容易写，所以括号是好处理的，因为左括号在一开始就出现，所以看到括号就可以递归expr()，这样就可以方便地处理所有嵌套的括号。

然后处理与和或，|和&因为是中缀的，所以麻烦一些，不好直接用递归来处理：我们看到数字的时候，并不能确定后面跟的是|还是&。但是我们观察到，这里的运算比较简单（|和&都可以从左到右积累进行），所以我们加入一系列状态变量来使得我们可以从左到右一遍扫描：

or_val, and_val跟踪到目前为止的积累“或”和“与”的结果。一个表达式最后是一个or的结果，其中每一项是and的结果，单个数字也是and的结果，括号内的表达式等价于一个数字。
shorts_or, shorts_and跟踪一共有多少次短路发生，或和与的短路分别计数。
or_short, and_short跟踪是否发生了短路。进入短路状态后，就不再累加短路次数。

这样就用一个状态机这样的方式，在一个函数里把|和&一起处理了。具体见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
char s[1000005];
int i;
 
// return (value, (number_of_and_shortcuts, number_of_or_shortcuts))
pair<int,pair<int,int>> expr(bool sh) {
    int shorts_or = 0, shorts_and = 0;
    bool or_val = false, or_short = false;
    bool and_val = true, and_short = false;
    while (i <= n) {
        char c = s[i];
        if (c == '(') {
            i++;
            pair<int,pair<int,int>> r = expr(sh | or_short | and_short);  // recurse on ()
            c = r.first ? '1' : '0';  // result becomes a single value
            shorts_and += r.second.first;
            shorts_or += r.second.second;
        }
        if (c == '&') {
            if (!and_val && !sh && !or_short) {
                shorts_and++;
                and_short = true;
            }
        }
        if (c == '|') {
            or_val |= and_val;
            if (or_val && !sh) {
                shorts_or++;
                or_short = true;
            }
            // restart "and" sequence
            and_short = false;
            and_val = true;
        }
        if (c == 0 || c == ')') {
            or_val |= and_val;
            break;
        }
        if (c == '0' || c == '1') {
            bool v = c == '1';
            and_val &= v;
        }
        i++;
    }
    return {or_val, {shorts_and, shorts_or}};
}
 
int main() {
    scanf("%s", s);
    n = strlen(s);
    pair<int,pair<int,int>> ans = expr(false);
    printf("%d\n%d %d\n", ans.first, ans.second.first, ans.second.second);
    return 0;
}