LeetCode刷题笔记-150-逆波兰表达式求值

题目信息

平台：LeetCode
题目：150. 逆波兰表达式求值
难度：中等
题目链接：逆波兰表达式求值

题目描述

给一个字符串数组 tokens，表示一个根据逆波兰表示法表示的算术表达式。

计算该表达式，返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/'。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是向零截断。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

初步思路

核心在于理解逆波兰表达式（后缀表达式）的计算方式。它的特点是：不需要考虑括号优先级，只要遇到运算符，就对前面最近的两个操作数进行运算即可。这种「后进先出」的特性天然适合用栈来实现。

算法分析

核心思想：栈模拟
技巧要点：遇到数字入栈，遇到运算符则弹出栈顶两个元素计算，结果再入栈；注意运算顺序，先弹出的是右操作数
时间复杂度：O(n)，只需遍历一次 tokens
空间复杂度：O(n)，栈的空间

逆波兰表达式小知识

表达式类型	遍历顺序	类比二叉树
前缀表达式	先访问运算符	前序遍历
中缀表达式	运算符在中间	中序遍历
后缀表达式（逆波兰）	先访问操作数	后序遍历

后缀表达式的优点：不需要括号，不需要考虑优先级，从左到右依次计算即可，方便计算机依次计算。

代码实现（C++）

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto c : tokens) {
            // 遇到数字直接入栈
            if (c != "+" && c != "-" && c != "*" && c != "/") {
                st.push(stoi(c));
            } else {
                // 遇到运算符，弹出栈顶两个元素
                int b = st.top(); st.pop();  // 右操作数
                int a = st.top(); st.pop();  // 左操作数

                if (c == "+") {
                    st.push(a + b);
                } else if (c == "-") {
                    st.push(a - b);
                } else if (c == "*") {
                    st.push(a * b);
                } else {
                    st.push(a / b);
                }
            }
        }
        return st.top();
    }
};

测试用例

输入	输出	说明
`["2","1","+","3","*"]`	`9`	`(2 + 1) * 3 = 9`
`["4","13","5","/","+"]`	`6`	`4 + (13 / 5) = 4 + 2 = 6`
`["10","6","9","3","+","-11","","/","","17","+","5","+"]`	`22`	复杂表达式，结果为 `22`

总结与反思

这道题是栈的经典应用之一，套路非常固定：遇到数字入栈，遇到运算符弹出两个数计算后再入栈。只要记住先弹出的是右操作数，顺序别搞反，基本就不会出错。

从这道题也能感受到，栈非常擅长处理「相邻元素消除/计算」类的操作。类似的题目还有前面我们做过的有效的括号、删除字符串中的所有相邻重复项等，都可以用类似的思路解决。

TK的小站