思路与算法

运算符栈按括号、&优先于|及左结合归约。每个子树保存值和两类短路次数，若左值短路则完全舍弃右子树的计数。

正确性说明

归约产生的子表达式按语法顺序正确。若左值决定结果，真正执行只包含左子树和当前一次短路；否则执行左右子树且无当前短路。归纳后的计数精确等于真实惰性求值执行过的节点。

复杂度

O(|s|)时间、O(|s|)栈空间，含输入与所有子表达式状态，不用深递归。

易错点

被外层短路跳过的右侧内部短路不计数；0&0&0按左结合产生两次短路。深括号不能递归爆栈。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct V {
    int v, a, o;
};
int main() {
    string s;
    cin >> s;
    vector<V> v;
    vector<char> ops;
    auto pri = [](char c) {
        return c == '&' ? 2 : c == '|' ? 1 : 0;
    };
    auto calc = [&]() {
        char op = ops.back();
        ops.pop_back();
        V b = v.back();
        v.pop_back();
        V a = v.back();
        v.pop_back();
        if (op == '&' && !a.v)
            a.a++;
        else if (op == '|' && a.v)
            a.o++;
        else {
            a.v = b.v;
            a.a += b.a;
            a.o += b.o;
        }
        v.push_back(a);
    };
    for (char c : s) {
        if (c == '0' || c == '1')
            v.push_back({c - '0', 0, 0});
        else if (c == '(')
            ops.push_back(c);
        else if (c == ')') {
            while (ops.back() != '(')
                calc();
            ops.pop_back();
        } else {
            while (!ops.empty() && pri(ops.back()) >= pri(c))
                calc();
            ops.push_back(c);
        }
    }
    while (!ops.empty())
        calc();
    cout << v.back().v << "\n" << v.back().a << ' ' << v.back().o << "\n";
}