当前位置: 首页>前端>正文

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]∗b[0]
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[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;
}

https://www.xamrdz.com/web/2vj1942375.html

相关文章: