Evaluate Reverse Polish Notation

Why it belongs on this sheet

This is simple stack mechanics, but it rewards calm implementation and correct operand ordering.

Pattern

Operand stack

Approach

Push numbers onto a stack. When an operator appears, pop the top two operands, apply the operator in the correct order, and push the result back.

Java solution

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
  public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (String token : tokens) {
      switch (token) {
        case "+":
          stack.push(stack.pop() + stack.pop());
          break;
        case "-":
          int rightSub = stack.pop();
          int leftSub = stack.pop();
          stack.push(leftSub - rightSub);
          break;
        case "*":
          stack.push(stack.pop() * stack.pop());
          break;
        case "/":
          int divisor = stack.pop();
          int dividend = stack.pop();
          stack.push(dividend / divisor);
          break;
        default:
          stack.push(Integer.parseInt(token));
      }
    }

    return stack.pop();
  }
}

Complexity

• Time: O(n)
• Space: O(n)

Interview note

Subtraction and division are where mistakes happen because order matters.