Evaluate Reverse Polish Notation

Problem

You are given an arithmetic expression written in **Reverse Polish Notation** (also called postfix notation). The expression arrives as an array of strings tokens, where each token is either an integer operand or one of the four binary operators "+", "-", "*", or "/". In Reverse Polish Notation, operators come **after** their two operands instead of between them. To evaluate the expression, scan the tokens left to right: push every operand onto a stack, and whenever you hit an operator, pop the top two values, apply the operator, and push the result back. The order matters — for the operands a (popped second) and b (popped first), the operation is a op b. Return the final integer value of the expression. Rules to keep in mind: - Division between two integers always **truncates toward zero** (for example, 7 / -3 is -2, not -3). - The given expression is always valid, so there is exactly one value left on the stack at the end. - Division by zero will never occur. The point of this format is that it needs no parentheses and no operator-precedence rules — the structure of the token sequence fully determines the order of evaluation.

Examples

Constraints

• 1 <= tokens.length <= 10^4
• Each token is either an operator in {"+", "-", "*", "/"} or an integer in the range [-200, 200] written without leading zeros.
• The input always represents a valid arithmetic expression in Reverse Polish Notation.
• All intermediate and final results fit within a signed 32-bit integer.
• No division by zero will occur.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.