2011NOIP普及组真题 4. 表达式的值

线上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]\ast b[0]$
$c[1]=a[1]\ast b[0]+a[1]\ast b[1]+a[0]\ast b[1]$

*号时：
$c[0]=a[0]\ast b[0]+a[1]\ast b[0]+a[0]\ast b[1]$
$c[1]=a[1]\ast 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;
}