• 150.逆波兰表达式求值 :::info 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
    逆波兰表达式：是一种后缀表达式，所谓后缀就是指算符写在后面。 :::

代码：（详细注释）

  1. class Solution {
  2. public:
  3.     int evalRPN(vector<string>& tokens) {
  4.         stack<int> st;
  5.         for (int i = 0; i < tokens.size(); i++) {
  6.             if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
  7.                 int num1 = st.top();
  8.                 st.pop();
  9.                 int num2 = st.top();
  10.                 st.pop();
  11.                 if (tokens[i] == "+") st.push(num2 + num1);
  12.                 if (tokens[i] == "-") st.push(num2 - num1);
  13.                 if (tokens[i] == "*") st.push(num2 * num1);
  14.                 if (tokens[i] == "/") st.push(num2 / num1);
  15.             } else {
  16.                 st.push(stoi(tokens[i]));
  17.             }
  18.         }
  19.         int result = st.top();
  20.         st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
  21.         return result;
  22.     }
  23. };

分析：
栈与递归之间在某种程度上是可以转换的！
逆波兰表达式相当于是二叉树中的后序遍历

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

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

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

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

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

stoi()

区别于atoi()

  • 都是C++的字符处理函数，把数字字符串转换成int输出

不同

  • atoi()的参数是 const char*
  • stoi()的参数是const string*
  • stoi()会做范围检查
  • atoi()不会做范围检查