线上OJ：
一本通:：http://ybt.ssoier.cn:8088/problem_show.php?pid=1956
核心思想1：
1、本题考的是表达式树。完整的方法可以先建树，然后再计算的方式。
2、但是本题涉及的运算符并不多，故也可以用栈来直接模拟计算。符号放入符号栈，数值放入数值栈
3、本题要求的是最终结果为 0 的方案数，鉴于如下原则
如果是 c=a+b，仅当 a=0, b=0时， c=0。a和b只要有一个为1，则 c=1
如果是 c=a*b，仅当 a=1, b=1时， c=1。a和b只要有一个为0，则 c=0
故，若a[0]、b[0]表示各自节点数值为0的方案数；a[1]、b[1]表示各自节点数值为1的方案数
+号时：
c
[
0
]
=
a
[
0
]
∗
b
[
0
]
c[0] = a[0] * b[0]
c[0]=a[0]∗b[0]
c
[
1
]
=
a
[
1
]
∗
b
[
0
]
+
a
[
1
]
∗
b
[
1
]
+
a
[
0
]
∗
b
[
1
]
c[1] = a[1]*b[0] + a[1]*b[1] +a[0]*b[1]
c[1]=a[1]∗b[0]+a[1]∗b[1]+a[0]∗b[1]
*号时：
c
[
0
]
=
a
[
0
]
∗
b
[
0
]
+
a
[
1
]
∗
b
[
0
]
+
a
[
0
]
∗
b
[
1
]
c[0] = a[0] * b[0] + a[1]*b[0] + a[0]*b[1]
c[0]=a[0]∗b[0]+a[1]∗b[0]+a[0]∗b[1]
c
[
1
]
=
a
[
1
]
∗
b
[
1
]
c[1] = a[1] * b[1]
c[1]=a[1]∗b[1]
4、综上所述，数值节点存储的应该是数组 a[0], a[1], 分别表示当前节点为0的方案总数 和 为1的方案总数。
核心思想2：
对于每一个待入栈的符号 s[i]
1、如果是左括号，则直接入栈
2、如果是右括号，则把符号栈内的符号全部算完，直到遇到第一个左括号时停止。然后把第一个左括号弹出（右括号也不入栈，相当于抵消一对括号）
3、如果是运算符
3.1 如果栈为空，直接入栈
3.2 如果栈顶是左括号，直接入栈
3.3 如果栈顶符号优先级更低或相同，直接入栈
3.4 如果栈顶符号优先级高，则把栈顶高优先级的符号全部算完，直至遇到第一个优先级更低或相同停止。然后符号入栈
3.5 注意1：栈顶不会遇到右括号，因为右括号和左括号已经抵消了
3.6 注意2：本题不需要校验表达式的合法性，否则还需要考虑括号要匹配；第一个不能是右括号；最后一个不能是左括号
4、叶子节点的数值都存入 {1,1}，因为叶子节点放0则为0，放1则为1，所以叶子节点值为0和1的总方案数都是1
题解代码：
#include <bits/stdc++.h>
#define MOD 10007
using namespace std;
stack<char> op;
stack<vector<int>> num; // num[0]表示该节点为0的方案数；num[1]表示该节点为1的方案数
int n;
string s;
int pri[128];
void inipri()
{
pri['+'] = 3; pri['*'] = 4;
}
void cal()
{
vector<int> a, b; // a, b为与 num 相同的结构
a = num.top(); // 数字栈取出第一个元素
num.pop(); // 并弹出
b = num.top(); // 数字栈取出第二个元素
num.pop(); // 并弹出
char c = op.top(); // 符号栈取出第一个运算符
op.pop(); // 并弹出
if(c == '+') // 如果是+，则左右均为0的方案数的乘积为新的0的方案数；0*1+1*0+1*1为新的1的方案数
num.push({(a[0] * b[0]) % MOD, (a[1]*b[1] + a[0]*b[1] + a[1]*b[0]) % MOD});
else // 如果是*，则左右均为1的方案数的乘积为新的1的方案数；0*1+1*0+0*0为新的0的方案数
num.push({(a[0]*b[0] + a[0]*b[1] + a[1]*b[0]) % MOD, (a[1] * b[1]) % MOD});
}
int main()
{
inipri(); // 初始化符号优先级
cin >> n >> s;
num.push({1, 1}); // 数字栈推的第一组数为 num[0]=1, num[1]=1。因为要么0，要么1，各有1种可能性
for(int i = 0; i < n; i++)
{
if(s[i] == '(') op.push(s[i]); // 如果是左括号，则直接入符号栈
else if(s[i] == ')') // 如果是右括号（右括号的优先级最低）
{
while( !op.empty() && op.top() != '(' ) cal(); // 则把符号栈内所有的运算符都算完，直到遇到第一个左括号
op.pop(); // 然后弹出栈顶的左括号。这样就完成了一对括号之间的计算
}
else // 如果读入的是*或者+
{
while( !op.empty() && pri[op.top()] > pri[s[i]] ) cal(); // 如果待入栈的符号优先级低于栈顶的符号，则把高优先级的运算符先计算
op.push(s[i]); // 符号加到栈中
num.push({1, 1}); // 每次新增的叶子节点放 0和1的方案数都是 1
}
}
while ( !op.empty() ) cal(); // 把所有运算符都计算完
cout << num.top()[0]; // 最后一个结果的[0] 即表示为0的方案总数
return 0;
}
