目录
1.题目描述
Kunkun学长觉得应该让学弟学妹了解一下这个知识点：后缀表达式相对于中缀表达式更容易让计算机理解和学习。
现在kunkun学长给出一串后缀表达式，你能帮他算出这个后缀表达式的值吗？
第一行输入后缀表达式长度n（1<=n<=25000）；
第二行输入一个字符串表示后缀表达式
（每个数据或者符号之间用逗号隔开，保证输入的后缀表达式合法，每个数包括中间结果保证不超过long long长整型范围）
2.输入输出
输入样例:
14
2,10,2,+,6,/,-
输出样例:
0
3.解题思路
后缀表达式，本质上就是给计算机读取的语言。
后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）
规则：从左向右扫描，遇到数字压栈，遇到操作符，弹出栈顶的两个元素，先弹出的元素在右边，后弹出来的在左边，进行计算后，将结果压栈，再往后扫描，直到扫描结束，输出栈顶元素，即为最终结果。
4.样例解析
下面以 14 2,10,2,+,6,/,-为例子来讲讲计算机的转换过程。
1. 首先读入 14 ，表示一共有14个字符
2.从左向右开始遍历表达式，首先遇到2, 将其入栈
栈的情况：2
3.从左向右开始遍历表达式，然后遇到10, 将其入栈
栈的情况：2,10
4.从左向右开始遍历表达式，然后遇到2, 将其入栈
栈的情况：2,10,2
5.从左向右开始遍历表达式，然后遇到+, 取出 2 和 10， 计算出 2 + 10 = 12，将12入栈
栈的情况：2,12
6.从左向右开始遍历表达式，然后遇到6, 将其入栈
栈的情况：2,12，6
7.从左向右开始遍历表达式，然后遇到 / , 取出10 和 6， 计算出 10 / 6 = 2 ，将 2 入栈
栈的情况：2,2
8.从左向右开始遍历表达式，然后遇到 - , 取出2 和 2， 计算出 2 - 2 = 0 ，将 0 入栈
栈的情况：0 （最后结果）
5.代码实现
🌈 5.1 数字情况
将其整个数字遍历，然后计算出数字的真实大小
if(s[i] >='0'&&s[i] <='9') { intj=i+1; while(s[j] >='0'&&s[j] <='9') j++ ; j-- ; for(; i<=j; i++ ) { tmp=tmp*10+ (s[i] -'0'); } q[++tt] =tmp; tmp=0, i=j; }
🌈 5.2 逗号情况
🌈 5.3 （坑点）负数的情况
elseif(s[i] =='-'&&s[i+1] >='0'&&s[i+1] <='9') { intj=i+1; i++ ; while(s[j] >='1'&&s[j] <='9') j++ ; j-- ; for(; i<=j; i++ ) { tmp=tmp*10+ (s[i] -'0'); } q[++tt] =tmp*-1; tmp=0, i=j; }
🌈 5.4 其他运算符的情况
记得整个原则： 先弹出的元素在右边，后弹出来的在左
else { LLnum1=q[tt-- ]; LLnum2=q[tt-- ]; if(s[i] =='+') q[++tt] =num1+num2; elseif(s[i] =='-') q[++tt] =num2-num1; elseif(s[i] =='*') q[++tt] =num2*num1; elseif(s[i] =='/') q[++tt] =num2/num1; }
完整代码
usingnamespacestd; typedeflonglongLL; intn; strings; LLq[25010]; inthh=0, tt=-1; intmain() { cin>>n; LLtmp=0; cin>>s; for(inti=0; i<n; i++ ) { if(s[i] >='0'&&s[i] <='9') { intj=i+1; while(s[j] >='0'&&s[j] <='9') j++ ; j-- ; for(; i<=j; i++ ) { tmp=tmp*10+ (s[i] -'0'); } q[++tt] =tmp; tmp=0, i=j; } elseif(s[i] ==',') continue; elseif(s[i] =='-'&&s[i+1] >='0'&&s[i+1] <='9') { intj=i+1; i++ ; while(s[j] >='1'&&s[j] <='9') j++ ; j-- ; for(; i<=j; i++ ) { tmp=tmp*10+ (s[i] -'0'); } q[++tt] =tmp*-1; tmp=0, i=j; } else { LLnum1=q[tt-- ]; LLnum2=q[tt-- ]; if(s[i] =='+') q[++tt] =num1+num2; elseif(s[i] =='-') q[++tt] =num2-num1; elseif(s[i] =='*') q[++tt] =num2*num1; elseif(s[i] =='/') q[++tt] =num2/num1; } } cout<<q[tt] <<endl; return0; }
