The O(n) Club: Evaluate Reverse Polish Notation — Now With 100% More Stack and 200% Less Parentheses

The O(n) Club: Evaluate Reverse Polish Notation — Now With 100% More Stack and 200% Less Parentheses

⚡ TL;DR

Evaluating expressions in Reverse Polish Notation (aka Postfix) is a classic “use a stack or suffer” interview puzzle. Push numbers, pop two for every operator, and please—keep your operands in the right order or the stack will judge your soul.

// Stack logic for RPN in Java:
Stack
<integer> stack = new Stack<>();
for (String token : tokens) {
    if ("+-*/".contains(token)) {
        int b = stack.pop();
        int a = stack.pop();
        switch (token) {
            case "+": stack.push(a + b); break;
            case "-": stack.push(a - b); break;
            case "*": stack.push(a * b); break;
            case "/": stack.push(a / b); break; // integer division (truncate)
        }
    } else {
        stack.push(Integer.parseInt(token));
    }
}
return stack.pop();</integer>

🧠 How Devs Usually Mess This Up

First mistake? Forgetting that “4 5 -” means 4 minus 5 — not the other way around. If your subtraction or division answers feel inside-out, you’re almost certainly flipping a and b. Also, division should truncate toward zero (just like Java’s boringly strict integer division), and tokens can easily be -42 or 107 — not just tidy little digits. There’s also the brave few who forgo stacks entirely, but we don’t talk about those people.

🔍 What’s Actually Going On

RPN is like ordering coffee for three friends and only combining their names at checkout. Every number/token sits on the stack, nervous, until an operator forces the top two to pair up and transform. You keep repeating: number in, wait; operator, pop two, push result. No extra rules, no parentheses, just hierarchy through the power of waiting your turn.

This works smoothly because stacks are last-in, first-out. Just like dirty laundry at a hackathon.

🛠️ PseudoCode

• Make a stack of Integers.

  Stack<Integer> stack = new Stack<>();

• Loop through the tokens array.

  for (String token : tokens)

• If token is an operator (+ - * /):
  • Pop second operand first (b), then first operand (a).
  • Do the math: a op b.
  • Push the result.

  int b = stack.pop();
  int a = stack.pop();
  stack.push(result);

• If token is a number (multi-digit, negative… bring it on):

  stack.push(Integer.parseInt(token));

• At end, pop and return the remaining answer.

💻 The Code

import java.util.Stack;
 public class RPNCalculator {
    public int evalRPN(String[] tokens) {
        Stack
<integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                int ans;
                switch (token) {
                    case "+": ans = a + b; break;
                    case "-": ans = a - b; break;
                    case "*": ans = a * b; break;
                    case "/": ans = a / b; break;
                    default: throw new IllegalArgumentException("Unknown op: " + token);
                }
                stack.push(ans);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
     private boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }
}
</integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Operand order: Subtract/divide as a op b, never b op a. This is the leading cause of silent suffering.
• Division: Java truncates toward zero, which is the right way for this problem—don’t second guess it.
• Token parsing: Expect negative/multi-digit tokens. “-1000” is legit.
• Stack underflow: Only blows up if your input is nonsense. Stand proud if your code explodes quickly on bad data.
• Time & Space: Both O(n), where n = tokens.length. Perfect for showing off your Big-O humility.

🧠 Interviewer Brain-Tattoo

“Reverse Polish Notation: Because parentheses are for the weak—and so is popping in the wrong order.”