Evaluate Reverse Polish Notation

Difficulty: Medium

Problem

An arithmetic expression is supplied in postfix form (Reverse Polish Notation) as an array of string tokens. Compute its integer value. The operators are '+', '-', '*' and '/'; each operand can be a number or the result of a smaller expression. Division of integers drops the fractional part, rounding toward zero. You can rely on the expression being valid.

Example

Input: tokens = ["9", "4", "-", "7", "2", "/", "*"]
Output: 15
Explanation: Reading left to right: 9 4 - gives 5, then 7 2 / gives 3 (truncated from 3.5), and finally 5 * 3 = 15.

Brute-force approach

Repeatedly find the first operator in the array, evaluate it with the two preceding numbers, replace all three with the result, and repeat until one number remains.

Steps

  1. While tokens has more than one element:
  2. Find the first operator in the list
  3. Get the two preceding numbers
  4. Evaluate and replace the triplet with the result
  5. Return the single remaining number

Time complexity: O(n²) · Space complexity: O(n)

Trade-offs

  • Array shifting/splicing on each operation is O(n)
  • Need to repeat up to n/2 times → O(n²) total
  • Modifying the original input array is messy

Optimal approach

Key insight: RPN is designed for stack evaluation: operands accumulate until an operator consumes them. One pass, O(n) time.

Use a stack: push numbers, and when an operator appears, pop two operands, evaluate, and push the result back. The final stack element is the answer.

Steps

  1. Initialize an empty stack
  2. For each token:
  3. If number: push onto stack
  4. If operator: pop b, pop a, push (a op b)
  5. Return the single element on the stack

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function evalRPN(tokens):
    stack = []
    
    for token in tokens:
        if token is an operator (+, -, *, /):
            b = stack.pop()
            a = stack.pop()
            stack.push(a operator b)
        else:
            stack.push(parseInt(token))
    
    return stack.pop()

Hints

  • Numbers get pushed onto the stack
  • When you see an operator, pop two numbers, apply the operator, push the result back
  • The first popped number is the right operand, the second is the left operand
  • Division should truncate toward zero (not floor)

Complexity questions

Why is the in-place reduction approach O(n²)?

Each reduction removes 2 elements with array shifting (O(n)), and we do ~n/2 reductions. Each reduction step requires shifting array elements → O(n). We perform about n/2 reductions → O(n²) total.

What is the time complexity of the stack-based evaluation?

O(n). We iterate through each token once, doing O(1) work per token (push or pop+push). Total: O(n).

What is the maximum stack size during evaluation?

O(n/2) ≈ O(n). At most, the stack holds all operands before any operators appear. For n tokens with ~n/2 operands, the stack size is O(n).

Check your understanding of Evaluate Reverse Polish Notation

What is Reverse Polish Notation (RPN)?

Operators come after their operands (postfix notation). RPN (postfix notation) places operators after their operands. '2 3 +' means 2 + 3. This eliminates the need for parentheses.

For tokens ['4', '13', '5', '/', '+'], which operation happens first?

13 / 5. In RPN, when we encounter '/', we pop the two most recent numbers: 5 (right) and 13 (left). So 13/5=2 happens first.

What does ['3', '4', '-'] evaluate to?

-1 (3 - 4). In RPN, '3 4 -' means 3 - 4 = -1. The operands appear in the same order as in normal notation: the first number (3) is the left operand.

Related problems

Keep practising