Skip to main content
Expression Evaluation

Reverse Polish Notation

In RPN, operators come AFTER their operands: '3 4 +' means 3+4. Evaluate with a stack: push numbers, when you see an operator, pop two numbers, compute the result, push it back. No parentheses needed!

O(n)
·
O(n)

How It Works

Reverse Polish Notation places operators after their operands — "3 4 +" means 3 + 4 — which removes any need for parentheses or precedence rules. Evaluation is a single left-to-right pass with a stack: push each number; on an operator, pop the top two values, apply the operation, and push the result. When the input ends, the lone value on the stack is the answer.

Every token is handled once with O(1) work, giving O(n) time and O(n) worst-case stack space. This is why compilers and calculators convert infix expressions to postfix first: once in RPN, evaluation is trivially linear with no lookahead.

Step-by-Step Visualization

Evaluate '2 1 + 3 *' in RPN
Input
2
1
+
3
*
Stack
2
ActionPush 2
1/4

Code

Java
static int evalRPN(String[] tokens) {
  Stack<Integer> stack = new Stack<>();

  for (String token : tokens) {
    if ("+-*/".contains(token)) {
      int b = stack.pop(), a = stack.pop();
      if (token.equals("+")) stack.push(a + b);
      else if (token.equals("-")) stack.push(a - b);
      else if (token.equals("*")) stack.push(a * b);
      else stack.push(a / b);
    } else {
      stack.push(Integer.parseInt(token));
    }
  }
  return stack.peek();
}

// Example: evalRPN(new String[]{"2","1","+","3","*"}) → 9

Tips & Gotchas

1Numbers go on the stack
2Operators pop two numbers, compute, push result back
3Second popped is left operand, first popped is right operand

Practice Problems

  • 1Evaluate Reverse Polish Notation
  • 2Basic Calculator II
  • 3Expression Add Operators

About the Expression Evaluation Pattern

Evaluate mathematical expressions by converting them into a format that's easy for a stack to process (like Reverse Polish Notation), or by using a stack to handle operator precedence and nested parentheses.

Key insight

Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).

Common Stack Interview Problems

  • Valid Parentheses
  • Next Greater Element
  • Largest Rectangle in Histogram
  • Trapping Rain Water
  • Daily Temperatures
  • Decode String

Frequently Asked Questions

Does operand order matter when I pop?

Yes, and it is the classic bug. For non-commutative operators, the first pop is the right operand and the second pop is the left one, so '13 5 −' computes secondPop − firstPop = 8. Getting subtraction and division backwards is the most common failure.

How does integer division behave with negatives here?

The standard problem requires truncation toward zero, so 6 / −132 should be 0 and −7 / 2 should be −3. Languages that floor division (like Python's //) need explicit truncation, such as int(a / b), to match the expected answers.