表达式求值(100pts)

• 将数字栈中的属性改成0和1的方案数,然后依据左右子树进行计算。

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
stack<char> ops;
stack<vector<int> > nums;
void cal()
{
    char c=ops.top();ops.pop();
    vector<int> b=nums.top();nums.pop(); //取出右子树 
    vector<int> a=nums.top();nums.pop(); //取出左子树 
    if(c=='+')
    {
        nums.push({a[0]*b[0]%mod,(a[0]*b[1]+a[1]*b[0]+a[1]*b[1])%mod});
        //计算加法中当前根为0和1的方案数 
    }
    else
    {
        nums.push({(a[0]*b[0]+a[0]*b[1]+a[1]*b[0])%mod,a[1]*b[1]%mod});
        //计算乘法中当前根为0和1的方案数 
    }
}
int main()
{
    int n;
    string expr;
    cin>>n>>expr;
    map<char,int> h={{'+',1},{'*',2}}; //初始化符合优先级 
    nums.push({1,1}); //第一个空格 
    for(char c:expr)
    {
        if(c=='(') ops.push(c); //左括号直接入栈 
        else if(c==')') //右括号 
        {
           while(ops.size()&&ops.top()!='(') cal(); //计算括号内 
           ops.pop();
        }
        else
		{
            while(ops.size()&&h[ops.top()]>=h[c]) cal(); //当前栈顶优先级大于等于当前字符 
            
            //左 
            nums.push({1,1}); //右 
            ops.push(c); //根 
        }
    }
    while(ops.size()) cal(); //计算剩余的符号 
    cout<<nums.top()[0]<<endl; //输出结果为数字0的方案数 
    return 0;
}