Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

What is this problem about?

The Evaluate Reverse Polish Notation interview question asks you to calculate the value of an arithmetic expression in RPN (also known as postfix notation). In RPN, operators follow their operands. For example, 3 4 + is equivalent to 3 + 4. This notation removes the need for parentheses and follows a strict "last-in, first-out" evaluation order. You are given an array of strings representing the expression, containing integers and operators (+, -, *, /).

Why is this asked in interviews?

Tech giants like Apple, Microsoft, and LinkedIn use this problem to test a candidate's knowledge of the Stack interview pattern. It’s a fundamental problem that checks if you understand operator precedence (which is inherent in RPN) and how to manage temporary results using a linear data structure. It also tests your ability to handle division rounding, especially with negative numbers.

Algorithmic pattern used

This problem is the textbook use case for a Stack.

1. Iterate through the tokens from left to right.
2. If the token is a number, push it onto the stack.
3. If the token is an operator:
   • Pop the top two elements from the stack (let them be b and a).
   • Note: the second pop is the first operand (a op b).
   • Perform the operation and push the result back onto the stack.
4. The final result is the only element left in the stack.

Example explanation

Tokens: ["2", "1", "+", "3", "*"]

1. Token "2": Push 2. Stack: [2]
2. Token "1": Push 1. Stack: [2, 1]
3. Token "+": Pop 1, Pop 2. 2 + 1 = 3. Push 3. Stack: [3]
4. Token "3": Push 3. Stack: [3, 3]
5. Token "*": Pop 3, Pop 3. 3 * 3 = 9. Push 9. Stack: [9] Result: 9.

Common mistakes candidates make

• Operand Order: Getting the order of operands wrong for subtraction and division (e.g., doing b - a instead of a - b).
• Integer Division: Forgetting that division in this problem usually truncates towards zero (which can be tricky with negative results in some languages).
• Empty Stack: Not handling edge cases like empty inputs, although usually the input is guaranteed to be valid.

Interview preparation tip

Reverse Polish Notation is the standard way calculators and compilers evaluate expressions. Practice converting standard "infix" notation (like 3 + 4) to postfix manually—this will help you visualize the stack operations better.