目录

1.题目描述

2.输入输出

3.解题思路

4.样例解析

5.代码实现

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] = '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  （坑点）负数的情况

else if(s[i] == '-' && s[i + 1] >= '0' && s[i + 1] = '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 {     LL num1 = q[tt -- ];     LL num2 = q[tt -- ];     if(s[i] == '+') q[++ tt] = num1 + num2;     else if(s[i] == '-') q[++ tt] = num2 - num1;     else if(s[i] == '*') q[++ tt] = num2 * num1;     else if(s[i] == '/') q[++ tt] = num2 / num1; }

完整代码 

#include #include #include using namespace std;typedef long long LL;int n;string s;LL q[25010];int hh = 0, tt = -1;int main(){    cin >> n;    LL tmp = 0;    cin >> s;    for(int i = 0; i = '0' && s[i] = '0' && s[j] <= '9') j ++ ; j -- ;     for(; i = '0' && s[i + 1] = '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 {     LL num1 = q[tt -- ];     LL num2 = q[tt -- ];     if(s[i] == '+') q[++ tt] = num1 + num2;     else if(s[i] == '-') q[++ tt] = num2 - num1;     else if(s[i] == '*') q[++ tt] = num2 * num1;     else if(s[i] == '/') q[++ tt] = num2 / num1; }    }    cout << q[tt] << endl;    return 0;}