Evaluate Reverse Polish Notation

Problem

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression.

Examples

The brute-force approach

Build the full expression tree by scanning the tokens and reconstructing nested parentheses, then evaluate the expression recursively. In practice, this approach requires a parser and is far more complex than the stack approach.

# No clean brute force exists, the stack IS the natural solution.
# A recursive tree approach requires scanning tokens twice: once
# to build the tree, once to evaluate.
# The stack linearizes this into a single left-to-right scan.

There's no simpler valid approach here, building an expression tree first is strictly more work than using a stack directly. This is one of those rare problems where the 'optimal' solution is also the most intuitive once you understand RPN.

Spotting the pattern

This is a Stack problem. The key question to ask yourself:

How do I always have the right two operands available the moment I encounter an operator?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.