How to Solve: Evaluate Reverse Polish Notation (RPN) – Complete Guide for FAANG Interviews

How to Solve: Evaluate Reverse Polish Notation (RPN) – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can handle stack-based evaluation, edge cases, and clean code under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling RPN, ensure you understand: 1. Stacks (LIFO) – Push/pop operations, time complexity (O(1) for both). 2. Basic arithmetic operations – How to evaluate +, -, , / with correct order of operations. 3. String parsing – Splitting tokens, converting strings to integers.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this every time you see an RPN problem:

1. Initialize a stack (empty list in Python).
2. Iterate through each token in the input list.
3. If token is a number:
4. Convert to integer and push onto stack.
5. If token is an operator:
6. Pop the top two elements (order matters: second = stack.pop(), first = stack.pop()).
7. Apply the operator (first OP second).
8. Push the result back onto the stack.
9. After loop ends:
10. If stack has exactly one element, return it.
11. Else, throw an error (invalid RPN).
12. Edge cases:
13. Division by zero → return error.
14. Single-element input → return the element.
15. Empty input → return error.

✅ WORKED EXAMPLES

Example 1 – Basic RPN

Problem: Evaluate ["2","1","+","3",""] → (2+1)3 = 9

Step-by-Step Execution

Final Answer: 9

Python Code

def evalRPN(tokens):

    stack = []

    for token in tokens:

        if token in "+-/":

            b = stack.pop()

            a = stack.pop()

            if token == "+": stack.append(a + b)

            elif token == "-": stack.append(a - b)

            elif token == "": stack.append(a  b)

            elif token == "/": stack.append(int(a / b))  # Truncate toward zero

        else:

            stack.append(int(token))

    return stack.pop()

Time Complexity: O(n) (one pass through tokens) Space Complexity: O(n) (stack size ≤ n/2)

Why this works: - Stack ensures correct order of operations (postfix evaluation). - Division truncates toward zero (Python’s int(a / b) behavior).

Example 2 – Medium (Division & Negative Numbers)

Problem: Evaluate ["4","13","5","/","+"] → 4 + (13/5) = 6

Step-by-Step Execution

Final Answer: 6

Python Code (Same as above)

def evalRPN(tokens):

    stack = []

    for token in tokens:

        if token in "+-/":

            b = stack.pop()

            a = stack.pop()

            if token == "+": stack.append(a + b)

            elif token == "-": stack.append(a - b)

            elif token == "": stack.append(a  b)

            elif token == "/": stack.append(int(a / b))

        else:

            stack.append(int(token))

    return stack.pop()

Edge Case: ["10","6","9","3","+","-11","","/","","17","+","5","+"] → 22 (Try this yourself!)

Why this works: - Handles negative numbers and division correctly. - Stack ensures operands are popped in reverse order (critical for - and /).

Example 3 – Hard (Follow-Up: Custom Operators)

Problem: Extend RPN to support exponentiation (^) and modulo (%).

Modified Python Code

def evalRPN(tokens):

    stack = []

    for token in tokens:

        if token in "+-/%^":

            b = stack.pop()

            a = stack.pop()

            if token == "+": stack.append(a + b)

            elif token == "-": stack.append(a - b)

            elif token == "": stack.append(a  b)

            elif token == "/": stack.append(int(a / b))

            elif token == "%": stack.append(a % b)

            elif token == "^": stack.append(a  b)

        else:

            stack.append(int(token))

    return stack.pop()

Test Case: ["2","3","^","4","%"] → (2^3) % 4 = 0

Why this works: - Extensible design: New operators require only one additional elif. - Same stack logic applies—no changes to the core algorithm.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. Reverse Polish Notation is all about stacks and order of operations. Here’s the playbook:

1. Initialize a stack—this is your evaluation engine.
2. Loop through tokens:
3. Numbers? Push.
4. Operators? Pop two, compute, push result.
5. Edge cases:
6. Division by zero? Error.
7. Final stack not size 1? Invalid RPN.
8. Code it cleanly—no eval(), no shortcuts.
9. Test with:
10. ["2","1","+","3",""] → 9
11. ["4","13","5","/","+"] → 6
12. ["10","6","9","3","+","-11","","/","","17","+","5","+"] → 22

You’ve got this. Walk in, write the stack, handle the edge cases, and you’ll crush it. Good luck!

? Final Notes

• Practice variations: Try RPN with floating-point numbers or custom operators.
• Time yourself: Aim for <10 minutes to code + test.
• Whiteboard first: Sketch the stack state for a few tokens before coding.

Now go ace that interview! ?