LeetCode 150: Evaluate Reverse Polish Notation (Stack Evaluation)
LeetCode 150StackExpressionSimulationToday we solve LeetCode 150 - Evaluate Reverse Polish Notation.
Source: https://leetcode.com/problems/evaluate-reverse-polish-notation/
English
Problem Summary
Given an array of tokens representing a Reverse Polish Notation expression, evaluate and return the integer result. Operators are +, -, *, /, and division truncates toward zero.
Key Insight
RPN naturally maps to a stack: push numbers, and when an operator appears, pop two values in order (left, right), compute, then push the result back.
Brute Force and Limitations
Building an expression tree is possible, but unnecessary for one-pass evaluation. A stack simulation is shorter, faster, and interview-friendly.
Optimal Algorithm Steps (Stack Simulation)
1) Initialize an empty stack of integers.
2) Scan each token from left to right.
3) If token is a number, parse and push it.
4) If token is an operator, pop right, then left, compute left op right, push result.
5) Final stack top is the answer.
Complexity Analysis
Time: O(n) where n is number of tokens.
Space: O(n) in the worst case.
Common Pitfalls
- Reversing operand order for subtraction/division.
- Using floor division instead of truncation toward zero in some languages.
- Forgetting negative integers are valid number tokens (e.g. -11).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> st = new ArrayDeque<>();
for (String t : tokens) {
switch (t) {
case "+": {
int b = st.pop(), a = st.pop();
st.push(a + b);
break;
}
case "-": {
int b = st.pop(), a = st.pop();
st.push(a - b);
break;
}
case "*": {
int b = st.pop(), a = st.pop();
st.push(a * b);
break;
}
case "/": {
int b = st.pop(), a = st.pop();
st.push(a / b);
break;
}
default:
st.push(Integer.parseInt(t));
}
}
return st.peek();
}
}func evalRPN(tokens []string) int {
st := make([]int, 0, len(tokens))
for _, t := range tokens {
switch t {
case "+", "-", "*", "/":
b := st[len(st)-1]
a := st[len(st)-2]
st = st[:len(st)-2]
var v int
switch t {
case "+":
v = a + b
case "-":
v = a - b
case "*":
v = a * b
case "/":
v = a / b
}
st = append(st, v)
default:
num, _ := strconv.Atoi(t)
st = append(st, num)
}
}
return st[len(st)-1]
}class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (const string& t : tokens) {
if (t == "+" || t == "-" || t == "*" || t == "/") {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (t == "+") st.push(a + b);
else if (t == "-") st.push(a - b);
else if (t == "*") st.push(a * b);
else st.push(a / b);
} else {
st.push(stoi(t));
}
}
return st.top();
}
};class Solution:
def evalRPN(self, tokens: List[str]) -> int:
st = []
for t in tokens:
if t in {"+", "-", "*", "/"}:
b = st.pop()
a = st.pop()
if t == "+":
st.append(a + b)
elif t == "-":
st.append(a - b)
elif t == "*":
st.append(a * b)
else:
st.append(int(a / b))
else:
st.append(int(t))
return st[-1]var evalRPN = function(tokens) {
const st = [];
for (const t of tokens) {
if (t === '+' || t === '-' || t === '*' || t === '/') {
const b = st.pop();
const a = st.pop();
if (t === '+') st.push(a + b);
else if (t === '-') st.push(a - b);
else if (t === '*') st.push(a * b);
else st.push((a / b) | 0); // truncate toward zero
} else {
st.push(Number(t));
}
}
return st[st.length - 1];
};中文
题目概述
给定一个表示逆波兰表达式（后缀表达式）的字符串数组 tokens，请计算表达式结果并返回整数值。运算符为 +、-、*、/，除法需向零截断。
核心思路
RPN 和栈是天然匹配：数字直接入栈；遇到运算符就弹出两个数（先右后左），计算后把结果压回栈中。
基线解法与不足
可以先构造表达式树再求值，但对这题来说步骤冗长。一次遍历 + 栈模拟更直接，代码更短也更稳定。
最优算法步骤（栈模拟）
1）准备一个整数栈。
2）从左到右遍历 tokens。
3）若是数字，解析后入栈。
4）若是运算符，弹出 right 与 left，计算 left op right 后再入栈。
5）遍历结束时，栈顶即答案。
复杂度分析
时间复杂度：O(n)。
空间复杂度：最坏 O(n)。
常见陷阱
- 减法/除法把左右操作数顺序写反。
- 某些语言用地板除导致与“向零截断”不一致。
- 忽略负数字符串（如 -11）其实是数字，不是运算符。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> st = new ArrayDeque<>();
for (String t : tokens) {
switch (t) {
case "+": {
int b = st.pop(), a = st.pop();
st.push(a + b);
break;
}
case "-": {
int b = st.pop(), a = st.pop();
st.push(a - b);
break;
}
case "*": {
int b = st.pop(), a = st.pop();
st.push(a * b);
break;
}
case "/": {
int b = st.pop(), a = st.pop();
st.push(a / b);
break;
}
default:
st.push(Integer.parseInt(t));
}
}
return st.peek();
}
}func evalRPN(tokens []string) int {
st := make([]int, 0, len(tokens))
for _, t := range tokens {
switch t {
case "+", "-", "*", "/":
b := st[len(st)-1]
a := st[len(st)-2]
st = st[:len(st)-2]
var v int
switch t {
case "+":
v = a + b
case "-":
v = a - b
case "*":
v = a * b
case "/":
v = a / b
}
st = append(st, v)
default:
num, _ := strconv.Atoi(t)
st = append(st, num)
}
}
return st[len(st)-1]
}class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (const string& t : tokens) {
if (t == "+" || t == "-" || t == "*" || t == "/") {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (t == "+") st.push(a + b);
else if (t == "-") st.push(a - b);
else if (t == "*") st.push(a * b);
else st.push(a / b);
} else {
st.push(stoi(t));
}
}
return st.top();
}
};class Solution:
def evalRPN(self, tokens: List[str]) -> int:
st = []
for t in tokens:
if t in {"+", "-", "*", "/"}:
b = st.pop()
a = st.pop()
if t == "+":
st.append(a + b)
elif t == "-":
st.append(a - b)
elif t == "*":
st.append(a * b)
else:
st.append(int(a / b))
else:
st.append(int(t))
return st[-1]var evalRPN = function(tokens) {
const st = [];
for (const t of tokens) {
if (t === '+' || t === '-' || t === '*' || t === '/') {
const b = st.pop();
const a = st.pop();
if (t === '+') st.push(a + b);
else if (t === '-') st.push(a - b);
else if (t === '*') st.push(a * b);
else st.push((a / b) | 0); // truncate toward zero
} else {
st.push(Number(t));
}
}
return st[st.length - 1];
};
Comments