0150. Evaluate Reverse Polish Notation
======================================
题目信息
--------
:题号: 0150. 逆波兰表达式求值
:难度: Medium
:主题: 栈、表达式树、后缀表达式、整数除法
:原题: `LeetCode 0150 `_
:重点: 用操作数栈保存已完成子表达式,按右后左的弹栈顺序执行二元运算,并准确区分负数与减号
题目重述
--------
给定字符串数组 ``tokens``,它构成一个有效的逆波兰表达式。每个 token 是整数或二元运算符 ``+``、``-``、
``*``、``/``;运算符作用于它前面最近完成的两个子表达式,较早者为左操作数、较晚者为右操作数。返回
整数结果。除法向零截断;输入保证不除零,所有中间值和最终值都在 32 位有符号整数范围内。
自建示例
--------
* ``["18", "5", "-", "4", "/"]``:先算 ``18-5=13``,再算 ``13/4=3``,返回 ``3``;
* ``["7", "-3", "*", "2", "+"]``:``-3`` 是数字,结果为 ``7*(-3)+2=-19``;
* ``["4", "13", "5", "/", "+"]``:先完成右侧子表达式 ``13/5=2``,再与 ``4`` 相加,返回 ``6``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
bool isOperator(const std::string& token) {
return token.size() == 1 &&
(token[0] == '+' || token[0] == '-' ||
token[0] == '*' || token[0] == '/');
}
int apply(int left, int right, char operation) {
if (operation == '+') {
return left + right;
}
if (operation == '-') {
return left - right;
}
if (operation == '*') {
return left * right;
}
return left / right;
}
int evaluateFromEnd(
const std::vector& tokens,
int& index
) {
const std::string& token = tokens[index];
--index;
if (!isOperator(token)) {
return std::stoi(token);
}
const int right = evaluateFromEnd(tokens, index);
const int left = evaluateFromEnd(tokens, index);
return apply(left, right, token[0]);
}
int evaluateWithOperandStack(
const std::vector& tokens
) {
std::vector operands;
operands.reserve(tokens.size());
for (const std::string& token : tokens) {
if (!isOperator(token)) {
operands.push_back(std::stoi(token));
continue;
}
const int right = operands.back();
operands.pop_back();
const int left = operands.back();
operands.pop_back();
operands.push_back(apply(left, right, token[0]));
}
return operands.back();
}
public:
int evalRPN(std::vector& tokens) {
return evaluateWithOperandStack(tokens);
}
};
题解
----
逆波兰顺序编码了怎样的表达式树
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
普通二元表达式树的后序遍历是“左子树、右子树、根运算符”。逆波兰表达式正是这个顺序:数字是叶子,每个
运算符在自己的两个子表达式都完整出现后才出现。因此不需要括号或优先级规则;读取运算符时,前面最近的
两个尚未被组合的结果就是它的左右孩子。
一种直接模拟是反复在 token 序列中寻找可计算的运算符,把它和前两个结果替换成一个数字。计算本身正确,
但数组删除、插入以及反复寻找位置会移动或扫描大量 token,最坏产生二次工作。栈可以只保留仍待父运算符
使用的子表达式结果。
操作数栈的不变量
~~~~~~~~~~~~~~~~
扫描任意合法前缀后,``operands`` 从底到顶保存若干已经完整求值、但尚未被后续运算符消费的子表达式结果。
读到数字时,它独立构成一个完成的叶子结果,压栈;读到运算符时,栈顶两个结果正是其右、左子表达式,弹出
并合成为一个新结果,再压回栈。
一次运算让栈元素数减少一:弹出两个、压回一个。完整有效表达式结束时,所有子树已组合为根,栈中恰好只
剩最终值。题目保证表达式有效,所以执行运算符时至少有两个操作数,代码不需要把非法输入分支混入核心
状态。
为什么第一次弹出的是右操作数
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
后缀片段 ``left right operator`` 表示 ``left operator right``。右子表达式更晚完成,所以结果位于栈顶;
第一次 ``pop`` 必须赋给 ``right``,第二次才是 ``left``。加法、乘法满足交换律,可能掩盖写反错误;减法
和除法会直接产生不同结果。
对 ``["18", "5", "-", "4", "/"]``:
.. list-table::
:header-rows: 1
* - token
- 操作前栈
- 操作后栈
* - ``18``
- ``[]``
- ``[18]``
* - ``5``
- ``[18]``
- ``[18, 5]``
* - ``-``
- ``[18, 5]``
- 先弹 ``right=5``、再弹 ``left=18``,压入 ``13``
* - ``4``
- ``[13]``
- ``[13, 4]``
* - ``/``
- ``[13, 4]``
- 计算 ``13/4``,得到 ``[3]``
负数字面量怎样与减号区分
~~~~~~~~~~~~~~~~~~~~~~~~
不能只看 token 的首字符:``"-3"`` 以减号开头却是整数,``"+12"`` 同理。只有 token 长度恰好为一,且
唯一字符属于四个运算符时,才按运算符处理;其余 token 交给 ``stoi``。单独的 ``"-"`` 是运算符,
``"-3"`` 不是。
反向递归展示了另一种状态解释
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
从 token 末尾读取,首先遇到整棵表达式树的根运算符。它前面紧邻的是右子表达式的末尾,所以
``evaluateFromEnd`` 必须先递归求右子树,再递归求左子树,最后调用同一个 ``apply(left, right)``。数字
直接作为叶子返回,引用参数 ``index`` 表示下一个尚未归属某棵子树的 token。
反向递归与正向栈访问同一表达式树,只是一个从根向叶解析,一个从叶向根归约。递归深度在极端倾斜表达式中
可达 ``O(n)``;显式操作数栈没有调用栈风险,因此作为主解。
除法与边界语义
~~~~~~~~~~~~~~
C++ 有符号整数除法向零截断,与题目一致:``13/4 == 3``,``-13/4 == -3``。输入保证右操作数非零且
所有中间结果不溢出,所以 ``apply`` 不需要额外饱和或异常分支。结果为负与负数字面量识别是两件独立事情:
栈中只保存已经解析好的整数。
主解选择与复杂度
~~~~~~~~~~~~~~~~
公开入口采用操作数栈。每个 token 解析、压栈或弹栈常数次,除数字转换所需字符时间外,总扫描为
``O(n)``;栈最坏 ``O(n)``。反向递归同为线性时间和最坏 ``O(n)`` 调用栈,保留它用于说明逆波兰表达式与
表达式树后序的对应,但迭代栈的状态和执行边界更稳健。