Evaluate Reverse Polish Notation - Solution & Explanation

Problem Overview: You receive an array of tokens representing a mathematical expression in Reverse Polish Notation (postfix form). Evaluate the expression and return the final integer result while handling operators like +, -, *, and /.

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

The natural way to evaluate Reverse Polish Notation is with a stack. Iterate through each token in the array. If the token is a number, push it onto the stack. If the token is an operator, pop the top two numbers from the stack, apply the operation in the correct order, and push the result back.

This works because postfix notation guarantees that every operator appears after its operands. The stack always holds intermediate results, and each operation reduces two values into one. Continue processing tokens until the end of the array; the stack's top element is the final result. Every token is processed exactly once, giving O(n) time complexity with O(n) space for the stack.

This problem directly tests your understanding of the stack data structure along with simple arithmetic from math. The tokens themselves are stored in an array, and the algorithm iterates through them sequentially.

Approach 2: Recursive Expression Evaluation (O(n) time, O(n) space)

Another way is to evaluate the expression recursively from the end of the token list. When you encounter an operator, recursively compute the right operand and then the left operand, then apply the operator. Each recursive call resolves a sub-expression and returns its value to the caller.

This approach mirrors how expression trees are evaluated, but it is less common in interviews because recursion makes the implementation harder to reason about and debug. It still processes each token once, resulting in O(n) time complexity, with O(n) space used by the recursion call stack.

Recommended for interviews: The stack-based approach is the expected solution. It directly models how postfix expressions are evaluated and demonstrates strong understanding of stacks and expression parsing. Showing awareness of recursive evaluation helps conceptually, but implementing the stack solution cleanly is what interviewers typically look for.