栈与队列5：逆波兰表达式求值

主要是我自己刷题的一些记录过程。如果有错可以指出哦&＃xff0c;大家一起进步。
转载代码随想录
原文链接&＃xff1a;
代码随想录
leetcode链接&＃xff1a;150. 逆波兰表达式求值

题目&＃xff1a;

根据 逆波兰表示法&＃xff0c;求表达式的值。

有效的算符包括 &＃43;、-、*、/ 。每个运算对象可以是整数&＃xff0c;也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说&＃xff0c;表达式总会得出有效数值且不存在除数为 0 的情况。

示例&＃xff1a;

示例 1&＃xff1a;

输入&＃xff1a;tokens &＃61; ["2","1","&＃43;","3","*"]
输出&＃xff1a;9
解释&＃xff1a;该算式转化为常见的中缀算术表达式为&＃xff1a;((2 &＃43; 1) * 3) &＃61; 9


示例 2&＃xff1a;

输入&＃xff1a;tokens &＃61; ["4","13","5","/","&＃43;"]
输出&＃xff1a;6
解释&＃xff1a;该算式转化为常见的中缀算术表达式为&＃xff1a;(4 &＃43; (13 / 5)) &＃61; 6


示例 3&＃xff1a;

输入&＃xff1a;tokens &＃61; ["10","6","9","3","&＃43;","-11","*","/","*","17","&＃43;","5","&＃43;"]
输出&＃xff1a;22
解释&＃xff1a;该算式转化为常见的中缀算术表达式为&＃xff1a;
((10 * (6 / ((9 &＃43; 3) * -11))) &＃43; 17) &＃43; 5
&＃61; ((10 * (6 / (12 * -11))) &＃43; 17) &＃43; 5
&＃61; ((10 * (6 / -132)) &＃43; 17) &＃43; 5
&＃61; ((10 * 0) &＃43; 17) &＃43; 5
&＃61; (0 &＃43; 17) &＃43; 5
&＃61; 17 &＃43; 5
&＃61; 22


提示&＃xff1a;

1 <&＃61; tokens.length <&＃61; 10⁴
tokens[i] 是一个算符&＃xff08;“&＃43;”、“-”、“*” 或 “/”&＃xff09;&＃xff0c;或是在范围 [-200, 200] 内的一个整数

逆波兰表达式&＃xff1a;
逆波兰表达式是一种后缀表达式&＃xff0c;所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式&＃xff0c;如 ( 1 &＃43; 2 ) * ( 3 &＃43; 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 &＃43; ) ( 3 4 &＃43; ) * ) 。
逆波兰表达式主要有以下两个优点&＃xff1a;

去掉括号后表达式无歧义&＃xff0c;上式即便写成 1 2 &＃43; 3 4 &＃43; * 也可以依据次序计算出正确结果。
适合用栈操作运算&＃xff1a;遇到数字则入栈&＃xff1b;遇到算符则取出栈顶两个数字进行计算&＃xff0c;并将结果压入栈中

思路&＃xff1a;

在上一篇文章中1047.删除字符串中的所有相邻重复项提到了 递归就是用栈来实现的。

所以栈与递归之间在某种程度上是可以转换的&＃xff01; 这一点我们在后续讲解二叉树的时候&＃xff0c;会更详细的讲解到。

那么来看一下本题&＃xff0c;其实逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点&＃xff0c;按照后序遍历的规则画出一个二叉树。

但我们没有必要从二叉树的角度去解决这个问题&＃xff0c;只要知道逆波兰表达式是用后续遍历的方式把二叉树序列化了&＃xff0c;就可以了。

在进一步看&＃xff0c;本题中每一个子表达式要得出一个结果&＃xff0c;然后拿这个结果再进行运算&＃xff0c;那么这岂不就是一个相邻字符串消除的过程&＃xff0c;和1047.删除字符串中的所有相邻重复项 (opens new window)中的对对碰游戏是不是就非常像了。
如动画所示&＃xff1a;

相信看完动画大家应该知道&＃xff0c;这和1047. 删除字符串中的所有相邻重复项 (opens new window)是差不错的&＃xff0c;只不过本题不要相邻元素做消除了&＃xff0c;而是做运算&＃xff01;
C&＃43;&＃43;代码如下&＃xff1a;

class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 力扣修改了后台测试数据&＃xff0c;需要用longlong
stack<long long> st;
for (int i &＃61; 0; i < tokens.size(); i&＃43;&＃43;) {
if (tokens[i] &＃61;&＃61; "&＃43;" || tokens[i] &＃61;&＃61; "-" || tokens[i] &＃61;&＃61; "*" || tokens[i] &＃61;&＃61; "/") {
long long num1 &＃61; st.top();
st.pop();
long long num2 &＃61; st.top();
st.pop();
if (tokens[i] &＃61;&＃61; "&＃43;") st.push(num2 &＃43; num1);
if (tokens[i] &＃61;&＃61; "-") st.push(num2 - num1);
if (tokens[i] &＃61;&＃61; "*") st.push(num2 * num1);
if (tokens[i] &＃61;&＃61; "/") st.push(num2 / num1);
} else {
st.push(stoll(tokens[i]));
}
}
int result &＃61; st.top();
st.pop(); // 把栈里最后一个元素弹出&＃xff08;其实不弹出也没事&＃xff09;
return result;
}
};


题外话

我们习惯看到的表达式都是中缀表达式&＃xff0c;因为符合我们的习惯&＃xff0c;但是中缀表达式对于计算机来说就不是很友好了。

例如&＃xff1a;4 &＃43; 13 / 5&＃xff0c;这就是中缀表达式&＃xff0c;计算机从左到右去扫描的话&＃xff0c;扫到13&＃xff0c;还要判断13后面是什么运算法&＃xff0c;还要比较一下优先级&＃xff0c;然后13还和后面的5做运算&＃xff0c;做完运算之后&＃xff0c;还要向前回退到 4 的位置&＃xff0c;继续做加法&＃xff0c;你说麻不麻烦&＃xff01;

那么将中缀表达式&＃xff0c;转化为后缀表达式之后&＃xff1a;[“4”, “13”, “5”, “/”, “&＃43;”] &＃xff0c;就不一样了&＃xff0c;计算机可以利用栈里顺序处理&＃xff0c;不需要考虑优先级了。也不用回退了&＃xff0c; 所以后缀表达式对计算机来说是非常友好的。

可以说本题不仅仅是一道好题&＃xff0c;也展现出计算机的思考方式。

在1970年代和1980年代&＃xff0c;惠普在其所有台式和手持式计算器中都使用了RPN&＃xff08;后缀表达式&＃xff09;&＃xff0c;直到2020年代仍在某些模型中使用了RPN。

自己的代码

#define LL long long
class Solution {
public:
int evalRPN(vector<string>& tokens) {
for (const string& ch : tokens) {
//符号就取出两个栈中元素做运算在加入栈中
if (ch &＃61;&＃61; "&＃43;" || ch &＃61;&＃61; "-" || ch &＃61;&＃61; "*" || ch &＃61;&＃61; "/") {
LL b &＃61; result.top();//算数符号右边
result.pop();
LL a &＃61; result.top();//算数符号左边
result.pop();
if (ch &＃61;&＃61; "&＃43;") {
result.push(a &＃43; b);
}
else if (ch &＃61;&＃61; "-") {
result.push(a - b);
}
else if (ch &＃61;&＃61; "*") {
result.push(a * b);
}
else if (ch &＃61;&＃61; "/") {
result.push(a / b);
}
}
else {//数字就转化一下压入栈中
result.push(stoll(ch));
}
}
return result.top();
}
private:
stack<LL>result;
/*int str2int(const string& str) {
int num &＃61; 0;
if (str[0] &＃61;&＃61; &＃39;-&＃39;) {
for (int i &＃61; 1; i num &＃61; num*10 &＃43; str[i] - &＃39;0&＃39;;
}
return -num;
}
else {
for (int i &＃61; 0; i num &＃61; num * 10 &＃43; str[i] - &＃39;0&＃39;;
}
return num;
}
}*/
};