当前位置：首页 > news >正文

面试常客逆波兰表达式：从原理到C++实现，搞定LeetCode 150. 逆波兰表达式求值

news 2026/5/3 5:38:38

逆波兰表达式全解析：从数学原理到LeetCode实战

在技术面试中，逆波兰表达式（Reverse Polish Notation, RPN）是一个高频考点，尤其出现在像LeetCode 150这样的经典题目中。但很多求职者仅仅停留在"会用栈解题"的层面，缺乏对背后原理的深入理解。本文将带你从数学表达式的本质出发，彻底掌握这一数据结构在表达式求值中的应用。

1. 为什么需要逆波兰表达式？

我们日常使用的数学表达式称为"中缀表达式"，如3 + 4 * 5。这种表示法对人类友好，但对计算机却存在两个主要问题：

运算符优先级处理复杂：需要额外规则确定运算顺序
括号嵌套难以解析：需要特殊处理括号匹配问题

波兰数学家Jan Łukasiewicz在1920年代提出了一种革命性的解决方案——后缀表示法（即逆波兰表达式）。它的核心特点是：

运算符位于操作数之后
完全消除括号需求
运算顺序由表达式结构唯一确定

关键优势对比：

特性	中缀表达式	逆波兰表达式
运算符位置	操作数之间	操作数之后
括号需求	需要	不需要
计算顺序	依赖优先级规则	由结构决定
计算机解析难度	复杂	简单

2. 中缀转后缀：栈的完美应用

理解转换算法是掌握逆波兰表达式的关键。我们通过一个具体例子3 * (4 + 5) - 6来演示转换过程：

2.1 转换步骤详解

初始化：
- 创建操作符栈op_stack
- 创建输出列表output
遍历处理：
- 遇到数字3：直接加入output→[3]
- 遇到*：栈空，入栈 →op_stack = [*]
- 遇到(：直接入栈 →op_stack = [*, (]
- 遇到4：加入output→[3, 4]
- 遇到+：栈顶是(，直接入栈 →op_stack = [*, (, +]
- 遇到5：加入output→[3, 4, 5]
- 遇到)：弹出直到(→
  - 弹出+加入output→[3, 4, 5, +]
  - 弹出(丢弃
- 遇到-：优先级≤栈顶*，先弹出*→
  - output = [3, 4, 5, +, *]
  - -入栈 →op_stack = [-]
- 遇到6：加入output→[3, 4, 5, +, *, 6]
最终处理：
- 弹出栈中剩余操作符 →output = [3, 4, 5, +, *, 6, -]

2.2 边界条件处理

在实际编码中，需要特别注意以下边界情况：

// 检查括号匹配 if (cur_op == ')') { while (!op_stack.empty() && op_stack.back() != '(') { output.push_back(op_stack.back()); op_stack.pop_back(); } if (op_stack.empty()) { throw runtime_error("Unmatched parentheses"); } op_stack.pop_back(); // 弹出'(' } // 处理连续数字 string current_num; while (i < s.size() && isdigit(s[i])) { current_num += s[i++]; } if (!current_num.empty()) { output.push_back(current_num); i--; // 回退一位 }

3. 后缀表达式求值：栈的再次登场

得到后缀表达式后，求值过程变得异常简单。继续以3 4 5 + * 6 -为例：

初始化：创建操作数栈num_stack
遍历处理：
- 3：入栈 →[3]
- 4：入栈 →[3, 4]
- 5：入栈 →[3, 4, 5]
- +：弹出5和4，计算4+5=9，入栈 →[3, 9]
- *：弹出9和3，计算3*9=27，入栈 →[27]
- 6：入栈 →[27, 6]
- -：弹出6和27，计算27-6=21，入栈 →[21]
结果：栈中唯一元素21即为最终结果

关键实现代码：

double evalRPN(vector<string>& tokens) { stack<double> st; for (const auto& token : tokens) { if (token.size() > 1 || isdigit(token[0])) { st.push(stod(token)); } else { double b = st.top(); st.pop(); double a = st.top(); st.pop(); switch (token[0]) { case '+': st.push(a + b); break; case '-': st.push(a - b); break; case '*': st.push(a * b); break; case '/': if (b == 0) throw runtime_error("Division by zero"); st.push(a / b); break; } } } return st.top(); }

4. LeetCode 150深度解析与优化

回到LeetCode 150题，我们不仅要正确解题，还要考虑面试官可能追问的优化点：

4.1 时间复杂度分析

转换阶段：O(n)，每个元素只处理一次
求值阶段：O(n)，每个元素处理一次
总体：O(n)线性时间复杂度

4.2 空间复杂度优化

常规实现使用两个栈（转换时一个，求值时一个），但可以优化：

就地转换：如果允许修改输入，可以在原数组上进行操作
合并步骤：边转换边计算，减少中间存储

int evalRPN(vector<string>& tokens) { stack<int> st; for (const auto& t : tokens) { if (t == "+" || t == "-" || t == "*" || t == "/") { int b = st.top(); st.pop(); int a = st.top(); st.pop(); st.push(t == "+" ? a + b : t == "-" ? a - b : t == "*" ? a * b : a / b); } else { st.push(stoi(t)); } } return st.top(); }