Evaluate Reverse Polish Notation - Solution & Explanation

Problem Overview: You are given an array of tokens representing an arithmetic expression written in Reverse Polish Notation (postfix). Evaluate the expression and return the final integer result. Operators appear after their operands, so you must process tokens in order and apply operations at the correct time.

Approach 1: Repeated List Reduction (O(n^2) time, O(1) extra space)

A straightforward way is to repeatedly scan the token array to find a pattern of number number operator. Once found, compute the result and replace the three elements with the computed value. Continue scanning and reducing the array until only one value remains. This works because postfix expressions guarantee that every operator eventually follows its operands. However, every reduction requires shifting elements or rebuilding the array, leading to O(n^2) time in the worst case. This approach is rarely used in production but helps you understand how postfix evaluation works.

Approach 2: Stack-Based Evaluation (O(n) time, O(n) space)

The standard solution uses a stack. Iterate through the tokens once. When you encounter a number, push it onto the stack. When you encounter an operator (+, -, *, /), pop the top two numbers from the stack, apply the operation, and push the result back. The order matters: the first popped value is the second operand. This works because postfix notation guarantees that operands appear before the operator that uses them.

Each token is processed exactly once, making the algorithm O(n) time. The stack may hold up to O(n) numbers in the worst case. This approach maps naturally to the structure of postfix expressions and is the standard interview solution. The implementation is straightforward in languages like Python, Java, and C++ using built-in stack or list structures.

The algorithm relies on simple operations: iterate through the array, push integers, and compute results using basic math operators. Division must truncate toward zero, which is a common edge case interviewers expect you to handle correctly.

Recommended for interviews: Interviewers expect the stack-based approach. It directly models how postfix expressions are evaluated and achieves optimal O(n) time. Mentioning the naive reduction idea shows conceptual understanding, but implementing the stack solution demonstrates practical problem-solving skill.