算法

(DP,树形DP,栈,表达式求值) $O(n)$

每一个中缀表达式都对应一棵满二叉树：

• 叶节点是数值；
• 内部节点是操作符，可能是+, *；

然后树形DP即可，每个节点存两个状态：该节点等于0的方案数、该节点等于1的方案数。

实际上我们也不需要将二叉树重建出来，直接在用栈模拟的过程中DP即可，这是因为栈模拟的顺序和深度优先遍历二叉树的顺序是相同的。

另外还要考虑在哪加入叶节点：

• 括号并不影响叶节点的位置，所以可以先忽略所有括号；
• 在剩下的每两个操作符之间填上数即可；

时间复杂度

整个算法的时间复杂度和深度优先遍历二叉树相同，都是 $O(n)$。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>

using namespace std;

const int N = 100010, mod = 10007;

stack<char> so;
stack<vector<int>> ss;

void eval()
{
    auto c = so.top(); so.pop();
    auto a = ss.top(); ss.pop();
    auto b = ss.top(); ss.pop();

    if (c == '+') ss.push({a[0] * b[0] % mod, (a[0] * b[1] + a[1] * b[0] + a[1] * b[1]) % mod});
    else ss.push({(a[0] * b[0] + a[1] * b[0] + a[0] * b[1]) % mod, a[1] * b[1] % mod});
}

int main()
{
    int n;
    string expr;
    cin >> n >> expr;

    map<char, int> pr;
    pr['('] = 0, pr['+'] = 1, pr['*'] = 2;

    ss.push({1, 1});
    for (auto c : expr)
    {
        if (c == '(') so.push(c);
        else if (c == '+' || c == '*')
        {
            while (so.size() && pr[so.top()] >= pr[c]) eval();
            ss.push({1, 1});
            so.push(c);
        }
        else
        {
            while (so.top() != '(') eval();
            so.pop();
        }
    }

    while (so.size()) eval();

    cout << ss.top()[0] << endl;

    return 0;
}