150. 逆波兰表达式求值
题目描述
输入字符串数组 tokens，它是一个用逆波兰表示法（后缀表达式）写成的算式。计算它的值，返回一个整数。
后缀表达式把运算符放在两个操作数后面，不需要括号。例如 (1 + 2) * (3 + 4) 写成 1 2 + 3 4 + *。从左往右扫描：遇到数字就压栈；遇到运算符就弹出两个数计算，再把结果压回去。先弹出的是右操作数。
运算符只有 +、-、*、/。整数除法的结果向零取整。输入保证是合法的表达式，不会出现除以 0，最终结果和中间结果都在 32 位整数范围内。
示例 1
输入：tokens = ["2","1","+","3","*"] 输出：9
解释：对应 (2 + 1) * 3 = 9。
示例 2
输入：tokens = ["4","13","5","/","+"] 输出：6
解释：对应 4 + 13 / 5，其中 13 / 5 取整为 2，结果 6。
示例 3
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22
解释：6 / -132 向零取整为 0，之后得到 0 + 17 + 5 = 22。
数据范围
1 <= tokens.length <= 10^4tokens[i]是+、-、*、/之一，或是[-200, 200]范围内的整数。
解题思路：栈
用栈。从左到右扫描：遇到数字就入栈；遇到运算符就弹出两个数，先弹出的是右操作数 b，再弹出的是左操作数 a，把 a op b 的结果压回栈。扫描结束后，栈里只剩一个数，就是答案。
为什么正确
栈中保存的是已经算好、但还没被后面运算符用掉的值，从栈底到栈顶按出现顺序排列。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
减法和除法不满足交换律，一定是“后弹出的 a”op“先弹出的 b”。除法要向零截断：Python 里 -7 // 2 = -4 是错的，要用 int(-7 / 2) = -3。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for t in tokens:
if t in '+-*/':
b = stack.pop()
a = stack.pop()
if t == '+':
stack.append(a + b)
elif t == '-':
stack.append(a - b)
elif t == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
else:
stack.append(int(t))
return stack[0]class Solution {
public int evalRPN(String[] tokens) {
Deque<Long> stack = new ArrayDeque<>();
for (String t : tokens) {
if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
long b = stack.pop();
long a = stack.pop();
if (t.equals("+")) {
stack.push(a + b);
} else if (t.equals("-")) {
stack.push(a - b);
} else if (t.equals("*")) {
stack.push(a * b);
} else {
stack.push(a / b);
}
} else {
stack.push(Long.parseLong(t));
}
}
return (int) (long) stack.peek();
}
}class Solution {
public:
int evalRPN(vector<string>& tokens) {
vector<long long> stack;
for (auto& t : tokens) {
if (t == "+" || t == "-" || t == "*" || t == "/") {
long long b = stack.back(); stack.pop_back();
long long a = stack.back(); stack.pop_back();
if (t == "+") {
stack.push_back(a + b);
} else if (t == "-") {
stack.push_back(a - b);
} else if (t == "*") {
stack.push_back(a * b);
} else {
stack.push_back(a / b);
}
} else {
stack.push_back(stoll(t));
}
}
return (int)stack[0];
}
};func evalRPN(tokens []string) int {
stack := []int{}
for _, t := range tokens {
if t == "+" || t == "-" || t == "*" || t == "/" {
b := stack[len(stack)-1]
a := stack[len(stack)-2]; stack = stack[:len(stack)-2]
if t == "+" {
stack = append(stack, a+b)
} else if t == "-" {
stack = append(stack, a-b)
} else if t == "*" {
stack = append(stack, a*b)
} else {
stack = append(stack, a/b)
}
} else {
v, _ := strconv.Atoi(t)
stack = append(stack, v)
}
}
return stack[0]
}var evalRPN = function(tokens) {
const stack = [];
for (const t of tokens) {
if (t === '+' || t === '-' || t === '*' || t === '/') {
const b = stack.pop();
const a = stack.pop();
if (t === '+') {
stack.push(a + b);
} else if (t === '-') {
stack.push(a - b);
} else if (t === '*') {
stack.push(a * b);
} else {
stack.push(Math.trunc(a / b));
}
} else {
stack.push(Number(t));
}
}
return stack[0];
};function evalRPN(tokens: string[]): number {
const stack: number[] = [];
for (const t of tokens) {
if (t === '+' || t === '-' || t === '*' || t === '/') {
const b = stack.pop()!;
const a = stack.pop()!;
if (t === '+') {
stack.push(a + b);
} else if (t === '-') {
stack.push(a - b);
} else if (t === '*') {
stack.push(a * b);
} else {
stack.push(Math.trunc(a / b));
}
} else {
stack.push(Number(t));
}
}
return stack[0];
}其他解法
栈从前向后扫描，用显式栈保存操作数；递归从后向前解析，用系统调用栈代替显式栈；两者时间和空间都是 O(n)。
解法 2：从后向前递归 时间 O(n)，空间 O(n)
逆波兰表达式的最后一个记号是整棵表达式树的根。用指针 pos 从末尾向前读：读到数字就直接返回；读到运算符，就先递归求出右操作数，再递归求出左操作数，最后计算结果。除法向零截断。
把表达式看成树来求值，体现后缀表达式和表达式树的对应关系。递归深度可能达到 n，需要注意调用栈上限。
import sys
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
sys.setrecursionlimit(max(10000, 2 * len(tokens) + 100))
self.pos = len(tokens) - 1
def calc():
t = tokens[self.pos]
self.pos -= 1
if t not in '+-*/':
return int(t)
b = calc()
a = calc()
if t == '+':
return a + b
if t == '-':
return a - b
if t == '*':
return a * b
return int(a / b)
return calc()class Solution {
private int pos;
private long calc(String[] tokens) {
String t = tokens[pos--];
if (!t.equals("+") && !t.equals("-") && !t.equals("*") && !t.equals("/")) return Long.parseLong(t);
long b = calc(tokens);
long a = calc(tokens);
if (t.equals("+")) return a + b;
if (t.equals("-")) return a - b;
if (t.equals("*")) return a * b;
return a / b;
}
public int evalRPN(String[] tokens) {
pos = tokens.length - 1;
return (int) calc(tokens);
}
}class Solution {
int pos;
long long calc(vector<string>& tokens) {
string& t = tokens[pos--];
if (t != "+" && t != "-" && t != "*" && t != "/") return stoll(t);
long long b = calc(tokens);
long long a = calc(tokens);
if (t == "+") return a + b;
if (t == "-") return a - b;
if (t == "*") return a * b;
return a / b;
}
public:
int evalRPN(vector<string>& tokens) {
pos = (int)tokens.size() - 1;
return (int)calc(tokens);
}
};func evalRPN(tokens []string) int {
pos := len(tokens) - 1
var calc func() int
calc = func() int {
t := tokens[pos]
pos--
if t != "+" && t != "-" && t != "*" && t != "/" {
v, _ := strconv.Atoi(t)
return v
}
b := calc()
a := calc()
switch t {
case "+":
return a + b
case "-":
return a - b
case "*":
return a * b
}
return a / b
}
return calc()
}var evalRPN = function(tokens) {
let pos = tokens.length - 1;
const calc = () => {
const t = tokens[pos--];
if (t !== '+' && t !== '-' && t !== '*' && t !== '/') return Number(t);
const b = calc();
const a = calc();
if (t === '+') return a + b;
if (t === '-') return a - b;
if (t === '*') return a * b;
return Math.trunc(a / b);
};
return calc();
};function evalRPN(tokens: string[]): number {
let pos = tokens.length - 1;
const calc = (): number => {
const t = tokens[pos--];
if (t !== '+' && t !== '-' && t !== '*' && t !== '/') return Number(t);
const b = calc();
const a = calc();
if (t === '+') return a + b;
if (t === '-') return a - b;
if (t === '*') return a * b;
return Math.trunc(a / b);
};
return calc();
}