Evaluate Reverse Polish Notation

Problem

You are given a list of string tokens representing an arithmetic expression written in postfix (Reverse Polish) notation. Each token is either an integer (possibly negative) or one of the four operators +, -, *, /. Evaluate the expression and return the integer result.

Rules:

• Operators apply to the two most recently produced values, in the order they were produced (so a b - means a - b).
• Division between integers truncates toward zero (so -7 / 2 is -3, not -4).
• There is no division by zero.
• The expression is always valid.

Constraints:

• The token list has between 1 and 25,000 entries.
• Every integer token, and every intermediate value, fits in a signed 32-bit integer.

Examples

• tokens = ["7", "3", "-", "5", "*"] → 20. Computes (7 - 3) * 5.
• tokens = ["15", "2", "4", "*", "/"] → 1. Computes 15 / (2 * 4); 15 / 8 truncates to 1.
• tokens = ["-9", "4", "/"] → -2. -9 / 4 is -2.25, and truncation toward zero gives -2, not the -3 that floor division would produce.

Hints

1. In postfix notation, by the time you reach an operator, its operands have already been fully evaluated. Where are they?
2. The two operands are the last two values you produced. Last-produced-first-consumed suggests a data structure.
3. Push numbers on a stack; on an operator pop two, apply, push the result. The single remaining value is the answer.