Evaluate Reverse Polish Notation
Understand the problem
Given an array tokens that represents an expression in postfix form (Reverse Polish Notation): operands come first, operators after. Evaluate the expression. The operators are +, -, *, /; division truncates toward zero.
Example:
tokens = ["2", "1", "+", "3", "*"]
// means (2 + 1) * 3 = 9
output = 9Postfix needs no parentheses: the order of the tokens already determines the order of evaluation.
Optimal solution
O(n) time, O(n) spacefunction evalRPN(tokens: string[]): number {
const stack: number[] = []
const ops: Record<string, (a: number, b: number) => number> = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
'/': (a, b) => Math.trunc(a / b),
}
for (const t of tokens) {
if (t in ops) {
const b = stack.pop()!
const a = stack.pop()!
stack.push(ops[t](a, b))
} else {
stack.push(Number(t))
}
}
return stack[0]
}The optimal solution uses a Stack to hold the pending operands.
- On a number, push it; on an operator, pop the 2 most recent numbers, compute, and push the result back.
- Mind the order: the number popped second (a) is the left operand and the one popped first (b) is the right operand — important for
-and/.
Step-by-step trace
1function evalRPN(tokens: string[]): number {2 const stack: number[] = []3 const ops: Record<string, (a: number, b: number) => number> = {4 '+': (a, b) => a + b,5 '-': (a, b) => a - b,6 '*': (a, b) => a * b,7 '/': (a, b) => Math.trunc(a / b),8 }9 for (const t of tokens) {10 if (t in ops) {11 const b = stack.pop()!12 const a = stack.pop()!13 stack.push(ops[t](a, b))14 } else {15 stack.push(Number(t))16 }17 }18 return stack[0]19}Edge cases to remember
Division truncates toward 0, NOT toward negative infinity:
6 / -132 = 0,7 / -2 = -3(not -4).Use
Math.trunc, notMath.floor.Negative numbers in tokens ("-11") — parse with
Number(t); don't confuse the minus sign of a negative number with the subtraction operator (an operator is always its own single-character token).Operand order: for "a b -" the result is a−b, not b−a; use the element popped second as the left-hand side.
An expression with a single number ["42"] → return 42, the loop never meets an operator.