思路与算法

用运算符栈恢复隐含变量，变量初值为(取0方案1,取1方案1)。按括号、乘优先和加优先级归约，保存每个子表达式的0/1方案数。

正确性说明

每个子表达式两侧变量互不共享，左右赋值方案可独立组合。或的0方案为左右0数乘积，与的1方案为左右1数乘积，其余由总方案减得。栈按规定优先级归约，因此根的0数是所求。

复杂度

O(L)时间和O(L)栈空间，含字符输入与栈初始化；L=0为一个变量。

易错点

符号+代表或而非异或；裸括号内也有变量。L=0时第二行为空，必须得到1种零值赋法。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int M = 10007;
struct V {
    int z, o;
};
int main() {
    int L;
    cin >> L;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    string s;
    getline(cin, s);
    vector<V> v;
    vector<char> op;
    auto calc = [&]() {
        char c = op.back();
        op.pop_back();
        V b = v.back();
        v.pop_back();
        V a = v.back();
        v.pop_back();
        int all = (a.z + a.o) * (b.z + b.o) % M,
            z = c == '+' ? a.z * b.z % M : (all - a.o * b.o % M + M) % M;
        v.push_back({z, (all - z + M) % M});
    };
    auto pri = [](char c) {
        return c == '*' ? 2 : c == '+' ? 1 : 0;
    };
    bool need = true;
    for (char c : s) {
        if (c == '(') {
            op.push_back(c);
            need = true;
        } else if (c == ')') {
            if (need)
                v.push_back({1, 1});
            while (op.back() != '(')
                calc();
            op.pop_back();
            need = false;
        } else {
            if (need)
                v.push_back({1, 1});
            while (!op.empty() && pri(op.back()) >= pri(c))
                calc();
            op.push_back(c);
            need = true;
        }
    }
    if (need)
        v.push_back({1, 1});
    while (!op.empty())
        calc();
    cout << v.back().z << "\n";
}