Repository navigation
053 — Evaluate Reverse Polish Notation
LeetCode 150 · Medium. Evaluate the value of an arithmetic expression given in Reverse Polish Notation (postfix notation). Valid operators are +, -, *, and /. Division between two integers truncates toward zero.
Normal ("infix") math writes the operator between its operands: 2 + 1. Reverse Polish Notation writes it after: 2 1 +. The reason RPN exists at all is that it removes every bit of ambiguity about order of operations — no parentheses, no precedence rules, ever needed. The trick to evaluating it: every time you read a number, set it aside. Every time you read an operator, it always applies to the two most recently set-aside numbers — never any earlier ones. Combine them, and the result goes back into the same "most recently set aside" pile, ready to be used by the next operator. That pile — always grabbing the most recent items first — is a stack.
"Reverse Polish Notation" / "postfix expression" / "evaluate an expression where operators come after their operands" is close to a literal keyword match for a stack: any expression-evaluation problem where an operator always consumes the most recently produced values needs LIFO order, not FIFO. This is a plain stack problem — there's no monotonic increasing/decreasing invariant being maintained here (values get pushed and popped based on token type, not based on comparisons between values), but it's built on the identical "grab what was most recently set aside" instinct that monotonic stacks specialize.
A candidate not thinking "stack" might instead repeatedly rescan the token list for the first operator, apply it to the two tokens immediately before it, splice the three tokens into a single result, and repeat — because in a valid RPN expression, the leftmost operator is always guaranteed to have exactly two operands sitting directly in front of it.
func evalRPNBruteForce(_ tokens: [String]) -> Int {
var tokens = tokens
let operators: Set<String> = ["+", "-", "*", "/"]
while tokens.count > 1 {
guard let opIndex = tokens.firstIndex(where: { operators.contains($0) }) else {
break
}
let b = Int(tokens[opIndex - 1])!
let a = Int(tokens[opIndex - 2])!
let op = tokens[opIndex]
let result: Int
switch op {
case "+": result = a + b
case "-": result = a - b
case "*": result = a * b
default: result = a / b
}
tokens.replaceSubrange((opIndex - 2)...opIndex, with: [String(result)])
}
return Int(tokens[0])!
}Big-O: O(n²) time — each of up to n / 2 reduction passes rescans the (shrinking) token list from the front and shifts elements during replaceSubrange. O(n) space for the mutable token copy.
Walk the tokens once. Push every number. On an operator, pop the two most recent operands, apply the operator, and push the result back — it's now available as an operand for whatever operator comes next.
func evalRPN(_ tokens: [String]) -> Int {
var stack: [Int] = []
for token in tokens {
switch token {
case "+", "-", "*", "/":
let b = stack.removeLast()
let a = stack.removeLast()
switch token {
case "+": stack.append(a + b)
case "-": stack.append(a - b)
case "*": stack.append(a * b)
default: stack.append(a / b) // Swift's Int division truncates toward zero, matching the problem's spec
}
default:
stack.append(Int(token)!)
}
}
return stack.removeLast()
}
// smoke test
print(evalRPN(["2", "1", "+", "3", "*"])) // 9 ((2 + 1) * 3)
print(evalRPN(["4", "13", "5", "/", "+"])) // 6 (4 + (13 / 5))
print(evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) // 22Big-O: O(n) time — one pass, O(1) work per token. O(n) space for the stack in the worst case (all numbers, no operators to shrink it).
The brute force treats "find the operator's two operands" as a fresh search over the whole remaining list every time, plus a shifting splice to fold the result back in. The optimal solution recognizes that operands are always consumed in exactly the reverse of the order they were read — a numbers-only pass hasn't "lost" any information the operator needs, because it's all sitting right at the top of the stack, in exactly the right order, the moment the operator is reached. Replacing "search + splice" with "pop twice, push once" turns an O(n²) reduction into a single O(n) pass.
- Stacks — the direct mechanism: numbers pushed, operators pop-compute-push, exactly the "evaluating expressions" use case called out in that chapter.
- Monotonic Stack — not a genuine match (nothing is compared or discarded based on value — every operand is used), but it's the closest pattern-family chapter here, sharing the same LIFO operand-ordering intuition.
-
Arrays & Strings — the token array being scanned and the numeric string parsing (
Int(token)) involved.
Evaluate Reverse Polish Notation is a pile of numbers waiting their turn — every operator that shows up always grabs the two most recently set-aside numbers, computes, and slides the answer right back onto the pile for the next operator to use.
Walk through ["4", "13", "5", "/", "+"] using the stack-based optimal solution, listing the stack's contents after each token is processed. Then explain why, if the tokens instead came in the invalid order ["4", "/", "13", "5", "+"], the very first removeLast() call would crash — what does that crash reveal about what "valid RPN" actually guarantees?