算法打卡第二十天｜LeetCode 150. 逆波兰表达式求值｜栈的经典应用

算法打卡第二十天｜LeetCode 150. 逆波兰表达式求值｜栈的经典应用

今天是算法打卡第20天，我学习了LeetCode 150. 逆波兰表达式求值这道题，作为栈的又一经典应用题，它的解题思路很巧妙，第一次接触很难直接想到解法，跟着视频讲解梳理逻辑后，彻底理解了栈在表达式计算中的核心作用，下面分享我的完整学习笔记。

题目回顾

题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/

题目描述

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
请你计算该表达式的值，返回整数结果。

逆波兰表达式（后缀表达式）规则：

- 整数（包括负数）作为运算数
- 运算符仅包含 + 、 - 、 * 、 /
- 每个运算符对应两个运算数，表达式始终有效
- 除法结果需向零截断（舍弃小数部分，保留整数）

示例

输入： tokens = ["2","1","+","3","*"]
输出： 9
解释：该逆波兰表达式对应普通算术表达式为 ((2 + 1) * 3) = 9

输入： tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出： 22

解题核心：为什么选择栈？

逆波兰表达式求值是栈的典型应用场景，这类表达式的计算逻辑天然适配栈的后进先出特性：

1. 逆波兰表达式的运算顺序：遇到数字则存储，遇到运算符则取出最近两个数字计算；
2. 栈可以完美记录遍历过程中的运算数，栈顶始终是最近的待运算数字；
3. 遇到运算符时，只需弹出两个栈顶运算数，计算后将结果重新入栈，最终栈中剩余数字就是表达式结果。

关键注意点：弹出的两个数字，先弹出的是右运算数，后弹出的是左运算数，减法和除法需注意运算顺序，避免计算错误！

详细解题思路

1. 初始化一个空栈，用于存储遍历过程中的运算数和中间计算结果；
2. 遍历字符串数组中的每一个元素：
- 如果当前元素是数字（包括负数），将其转换为整数后入栈；
- 如果当前元素是运算符：
- 弹出栈顶第一个元素，作为右运算数；
- 弹出栈顶第二个元素，作为左运算数；
- 根据运算符执行对应计算，除法需遵循向零截断规则；
- 将计算结果重新压入栈中；
3. 遍历完成后，栈中仅剩一个数字，即为表达式最终求值结果。

代码实现

整理了常用语言的实现代码，逻辑清晰，贴合解题思路：

C++ 实现

cpp
class Solution {
public:
int evalRPN(vector<string>& tokens) {
<long long> st; // 用long long避免数值溢出
for (auto& token : tokens) {
// 判断是否为运算符
if (token == "+" || token == "-" || token == "*" || token == "/") {
// 弹出右运算数、左运算数
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
// 执行对应运算
if (token == "+") st.push(num2 + num1);
if (token == "-") st.push(num2 - num1);
if (token == "*") st.push(num2 * num1);
if (token == "/") st.push(num2 / num1);
} else {
// 数字转换为整数入栈
st.push(stoll(token));
}
}
return st.top();
}
};


Python 实现

python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token in '+-*/':
num1 = stack.pop()
num2 = stack.pop()
if token == '+':
stack.append(num2 + num1)
elif token == '-':
stack.append(num2 - num1)
elif token == '*':
stack.append(num2 * num1)
else:
# 除法向零截断
stack.append(int(num2 / num1))
else:
stack.append(int(token))
return stack[0]


Java 实现

java
class Solution {
public int evalRPN(String[] tokens) {<Integer><>();
for (String s : tokens) {
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
int num1 = stack.pop();
int num2 = stack.pop();
switch (s) {
case "+":
stack.push(num2 + num1);
break;
case "-":
stack.push(num2 - num1);
break;
case "*":
stack.push(num2 * num1);
break;
case "/":
stack.push(num2 / num1);
break;
}
} else {
stack.push(Integer.parseInt(s));
}
}
return stack.pop();
}
}


复杂度分析

- 时间复杂度：O(n)，n为字符串数组长度，每个元素仅入栈、出栈一次，遍历一次即可完成计算；
- 空间复杂度：O(n)，最坏情况下栈中存储所有运算数，占用n个空间。

学习心得

这道题让我对栈的应用有了更深刻的理解，看似复杂的表达式计算，借助栈后进先出的特性，就能轻松解决。第一次接触逆波兰表达式确实会无从下手，但理清「数字入栈、运算符取数计算」的核心逻辑后，会发现栈完美解决了「寻找最近运算数」的问题。

同时也总结了这类栈表达式题的易错点：减法和除法的运算数顺序不能颠倒，一定要牢记先弹出的是右运算数，后弹出的是左运算数。

后续遇到中缀表达式转后缀表达式、括号匹配、相邻元素消除等问题，都可以第一时间想到用栈解决，栈的核心就是记录最近状态、快速回溯处理！

学习资料

- 题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/
- 视频讲解：https://www.bilibili.com/video/BV1kd4y1o7on