题解 P1981 [表达式求值 ]

diu· · 2018-10-30 12:26:28 · 题解

本题对熟用栈的大佬应该很容易

本蒟蒻还是想用栈讲解一下

首先是思路：

• 可以用一个栈储存运算符

• 并用另一个栈储存需要运算的数字

• 好了,其它的代码注释里面很清楚了

上代码：

# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <stack>
using namespace std;

stack<int>num;                                  //存数字
stack<char>ysf;                                 //存运算符
string js;                                      //输入的数据
int sum=0,ans,t,t1,t2;                          //t,t1,t2均为临时变量

int main()
{
    cin>>js;
    for(int i = 0;i < js.length();i++)
    {
        if(js[i] >= '0'&&js[i] <= '9')          //字符转数字
        {
            if(js[i+1] >= '0' && js[i+1] <= '9')
                sum=sum*10+js[i]-'0';
            else                                //若下一位为运算符就压如数字
            {
                sum=(sum*10+js[i]-'0')%10000;   //取模,后四位
                num.push(sum);
                sum=0;
            }
        }
        if(js[i] < '0')                         //运算符
        {
            if(ysf.empty())
                ysf.push(js[i]);
            else
            {
                if(js[i] < ysf.top())
                    ysf.push(js[i]);
                else                            //保证运算符栈里面de运算优先级
                {                               //同级都不行
                    t1=num.top();num.pop();
                    t2=num.top();num.pop();

                    if(ysf.top()=='*')
                        t=(t1*t2)%10000;
                    else
                        t=(t1+t2)%10000;

                    ysf.pop();

                    ysf.push(js[i]);
                    num.push(t);
                }
            }
        }
    }

    while(!ysf.empty())
    {
        t1=num.top();num.pop();
        t2=num.top();num.pop();
        char x=ysf.top();ysf.pop();

        if(x=='+')
        {
            t=(t1+t2)%10000;
            num.push(t);
        }
        else
        {
            t=(t1*t2)%10000;
            num.push(t);
        }
    }
    ans=num.top();                          //可直接输出栈顶元素

    cout<<ans<<endl;

    return 0;
}

><

￣▽￣(此符号未必没用哦~)