PTA后缀式求值（整型版）

作者 周强

单位 青岛大学

我们人类习惯于书写“中缀式”，如 3 + 5 * 2 ，其值为13。 (p.s. 为什么人类习惯中缀式呢？是因为中缀式比后缀式好用么？）

而计算机更加习惯“后缀式”（也叫“逆波兰式”，Reverse Polish Notation）。上述中缀式对应的后缀式是： 3 5 2 * +

现在，请对输入的后缀式进行求值。为了简化输入处理和运算，运算数（操作数）不超过30个且均为不超过5位的正整数，运算符（操作符）仅有+ - * /（加减乘除）四种。题目保证运算的中间结果和最终结果都在整型范围内，且不会出现除数为0的情况。

输入格式:

第一行给出一个不超过10的正整数k；

接下来k行，每行给出一个后缀式，以=号结束，运算符、运算数和=号之间均以一个空格间隔。

输出格式:

输出有k行，对于所输入的每个后缀式，判断是否正确（可求值），并在一行里输出：

• 如果后缀式无误、可求值，输出结果
• 如果后缀式错误，则输出Expression Error!

输入样例1:

2
1 2 3 4 + - * =
10 2 3 + / 4 * 5 - =

输出样例1:

-5
3

输入样例2:

2
10 2 / =
10 2 + - =

输出样例2:

5
Expression Error!

注意点：

1、后缀有符号时，单调栈里面至少需要有两个数 。

2、在最后读到等号时，栈里面只能有一个数字。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"stack<ll>st;//单调栈 
string s;//读取字符 void solve(){ll x,y;bool f=1;//判断是否有1违法状态 while(!st.empty())st.pop();//清空栈 while(cin >> s){if(s == "=")break;//读入结束 if(!f)continue;if(s[0] >= '0' && s[0] <= '9'){//题目保证没有负数 x=stol(s);}else{if(!st.empty())y=st.top(),st.pop();else f=0;if(!st.empty())x=st.top(),st.pop();else f=0;if(!f)continue;if(s == "*")x*=y;if(s == "/")x/=y;if(s == "-")x-=y;if(s == "+")x+=y;}st.push(x);}if(f && st.size() == 1)cout << st.top() << endl;else cout << "Expression Error!" << endl;return;
}int main(){ll t=1;cin >> t;while(t--)solve();return 0;
}