Evaluate Reverse Polish Notation

Difficulty: Medium

Problem

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (postfix notation). Evaluate the expression and return an integer that represents the value. Valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. Division between two integers should truncate toward zero. The input is guaranteed to be a valid RPN expression.

Example

Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9. First compute 2+1=3, then 3*3=9.

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)