1.题目描述

LeetCode题目链接

在这里插入图片描述

逆波兰表达式由波兰的逻辑学家卢卡西维兹提出。逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也称后缀表达式。

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

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

在进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程，和 “删除字符串中的所有相邻重复项”中的对对碰游戏是不是就非常像了。

动图链接

看完动画应该知道，这和删除字符串中的所有相邻重复项是差不多的，只不过本题不要相邻元素做消除了，而是做运算！

2. 思路

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

如果遇到操作数，则将操作数入栈；
如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

3.代码实现

3.1 c++实现

class Solution {
public:int evalRPN(vector<string>& tokens) {stack <int> st;for(int i=0;i < tokens.size();i++){if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){int rightnum = st.top();st.pop();int leftnum = st.top();st.pop();if(tokens[i] == "+")st.push(leftnum + rightnum); if(tokens[i] == "-")st.push(leftnum - rightnum);  if(tokens[i] == "*")st.push(leftnum * rightnum); if(tokens[i] == "/")st.push(leftnum / rightnum); }else{st.push(stoi(tokens[i]));}}int result = st.top();st.pop();// 把栈里最后一个元素弹出（其实不弹出也没事）return result;}
};