Evaluate Reverse Polish Notation

Reverse Polish Notation (RPN), also known as postfix notation, is a useful format for calculators and expression evaluation because it eliminates the need for parentheses. In RPN, operators like + and * follow their operands instead of being placed in between them, like in standard infix notation. In an interview, evaluating an RPN expression tests your ability to parse tokens in order and manage intermediate state efficiently.

Problem Statement

Given an array of string tokens representing an arithmetic expression in Reverse Polish Notation, evaluate the expression and return the result. Valid operators are +, -, *, and /. Division between two integers should truncate toward zero. You may assume the given RPN expression is always valid and that division by zero does not occur.

// Signature in a technical interview:
public int evalRPN(String[] tokens);

1. Clarify Requirements Before Jumping Into Code

• Tokens are either valid integers (possibly negative) or one of the four operators.

• Division should truncate toward zero (e.g. -3/2 == -1).

• No division by zero will occur.

2. Identify the Category of the Question

This is an expression evaluation problem using a stack. Common patterns include:

• Stack-based parsing for postfix or prefix notation

• Shunting-yard algorithm for infix-to-postfix conversion

• Recursion for tree-based evaluation

• Two-pass with operator precedence for infix

RPN maps directly to a stack: push operands, pop two for each operator, then push the result.

3. Consider a Brute‑Force Approach to Understand the Problem

A brute-force but inefficient idea is to:

1. Convert the token array into a dynamic list.

2. Scan from left to right, and whenever you see an operator at index i, parse the two previous tokens i-2 and i-1. We can compute the result and replace tokens i-2..i with the single result string. Then we just restart scanning from the beginning.

   
   

Time: O(n²)

Space: O(n)

This works, but it is incredibly inefficient because a list forces us to shift O(n) elements every time we process an operator. That gives us a runtime of O(n²).

So while this is probably not the solution we want, it can point us in the right direction: if our runtime is hurt because our choice of data structure is inefficient, is there another data structure that might be better?

4. Brainstorm More Solutions

Let's start brainstorming some more ideas.

Part of what makes this question interesting is the fact that coding languages don't typically come with a built-in mechanism for evaluating Reverse Polish Notation. So to solve this problem, ultimately we need to find a way to convert this problem to something we do know how to handle: we need to convert the question to standard infix notation (i.e. "5+5" instead of "5 5 +")?

How do we do that?

Option 1: Parse and insert parentheses

Building off our brute-force solution, what if instead of processing the input in-place, we start from scratch with a new list to hold our elements? Then instead of shifting elements, we can simply insert them to the end of our list in constant time?

We would process the input the same way: iterate through elements, and each time we find an operator, put parentheses around the two previous elements and insert them into our result list.

Then we can just process the result list! We can process the array in one pass, giving us O(n) runtime and O(n) space.

The code for this solution might be a bit complicated though. You'd need to be careful about edge cases and off-by-one errors. Is there another option?

Option 2: Stack evaluation

Our brute-force solution helped us ask a very good question: since the inefficient runtime is due in part to the inefficiencies of the data structure that we chose, is there another data structure that might be better?

I know the whole of RPN is that operands come before their operator. As I process left-to-right, every time I see an operator, the two most recent values belong to it.

So, is there a data structure that would allow me to access the "most recent" values in constant time? The data structure should not require shifting of elements, should allow me to access the elements in last-in first-out order, and should allow me to pop and push elements in constant time.

The answer: a stack!

So, as I walk through tokens in order:

• Push integer tokens onto a stack

• When I encounter an operator, pop the top two values, apply the operator in correct order, and push the result

• At the end, the stack should contain just a single element - our answer!

This solution is also O(n) runtime and O(n) space, but should lead to code that is much cleaner and easier to follow - an important detail that's easy to forget when you're in the middle of an interview!

Option 3: Binary Tree While our previous solution is very good, for the sake of completeness, we should still ask the question: Are there other data structures that might also work here?

Let's ask: what are we building towards in our solution? We're building towards a single element, where that element is calculated from two operands. The trick - each operand could also be considered it's own result that is calculated from two operands.

What data structure comes to mind when we think about a single top element and two sub-elements that connect to it? A binary tree! Each node is an operand and the children are the two values that proceeded that operand.

This feels like overkill though. The code would be complicated and we don't really gain anything meaningful from that code - we still have an O(n) runtime and O(n) space solution. So this solution, while clever and shows off your grasp of trees, probably isn't the solution you'll want to pick.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
List replacement (brute‑force)	O(n²)	O(n)	Conceptually simple	Quadratic time, complex shifts
Parse tree recursion	O(n)	O(n) stack	Generalizes to any notation	Heavy parsing, recursion depth
Infix conversion + eval	O(n)	O(n)	Reuses infix solver	Complex conversion overhead
Stack-based one-pass (optimal)	O(n)	O(n)	Simple, direct, O(1) per token	Stack space O(n)

Stack-based evaluation is clearly optimal for RPN.

6. Write Pseudocode to Structure Your Thoughts

function evalRPN(tokens):
  create empty stack
  for each token in tokens:
    if token is an operator:
      b = stack.pop()
      a = stack.pop()
      result = apply(token, a, b)
      stack.push(result)
    else:
      stack.push(parseInt(token))
  return stack.pop()

7. Consider Edge Cases

• Single token: ["42"] → returns 42.

• Operators in sequence: always valid per problem guarantee.

• Negative numbers: ["-3","2","*"] → -6.

• Division truncation: ["-3","2","/"] → -1.

• Large expressions: deep stack usage but within constraints.

8. Write Full Code Syntax (in Java)

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

public class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-": {
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a - b);
                    break;
                }
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/": {
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a / b); // truncates toward zero
                    break;
                }
                default:
                    stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Test 1: simple add
    assert sol.evalRPN(new String[]{"2","1","+","3","*"}) == 9;
      // (2 + 1) * 3 = 9

    // Test 2: with division and subtraction
    assert sol.evalRPN(new String[]{"4","13","5","/","+"}) == 6;
      // 4 + (13 / 5) = 6

    // Test 3: single number
    assert sol.evalRPN(new String[]{"42"}) == 42;

    // Test 4: negative numbers and multiplication
    assert sol.evalRPN(new String[]{"-3","2","*"}) == -6;

    // Test 5: division truncation
    assert sol.evalRPN(new String[]{"-3","2","/"}) == -1;

    // Test 6: complex expression
    String[] expr = {"5","1","2","+","4","*","+","3","-"};
    // 5 + ((1 + 2) * 4) - 3 = 14
    assert sol.evalRPN(expr) == 14;

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Stack-based evaluation is the canonical solution for postfix notation.

• Switch on operators with careful operand order (a then b).

• Truncating division in Java matches problem requirements.

• Single-pass over tokens yields O(n) time and O(n) stack space.

• Sketching clear pseudocode before coding prevents mis‑ordering pops and pushes.

• Discussing multiple approaches and their trade‑offs shows depth before implementing the optimal stack method.

• Don't forget to consider code complexity when choosing your optimal solution!

Good Luck and Happy Coding!