Stacks and Queues Matching and cancelling
196. Evaluate Reverse Polish Notation
You are given an arithmetic expression in postfix notation as a list of strings tokens, one token per
element. Each token is an integer or one of the four operators +, -, * and /. Return the value of the
expression.
In postfix notation an operator comes after its two operands. Each operator works on the two values that come
right before it, where a value is a number or the result of an earlier operation, and the earlier of the two
is the left operand. So ["8", "3", "-"] means 8 − 3 = 5, and ["2", "3", "4", "*", "+"] means
2 + 3 × 4 = 14. Brackets are never needed, because the order of the tokens fixes the order of the operations.
Division between two integers truncates toward zero: 7 / 2 is 3, and −7 / 2 is −3. A negative number is
written with its sign, such as "-3".
Example 1
Input: tokens = ["6", "2", "8", "+", "3", "/", "-"]
3Explanation: First 2 + 8 = 10, then 10 / 3 = 3 with the remainder dropped, and last 6 − 3 = 3. In ordinary notation this is 6 − (2 + 8) / 3.
Example 2
Input: tokens = ["7", "-2", "/", "-5", "*"]
15Explanation: 7 / −2 is −3.5, and truncating toward zero gives −3, not −4. Then −3 × −5 = 15.
Example 3
Input: tokens = ["-42"]
-42Explanation: A single number is a complete expression, and its value is the number itself.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ tokens.length ≤ 105- Each
tokens[i]is"+","-","*","/"or an integer from-109to109, written in decimal with no leading zeros tokensis a valid postfix expression- No division has a divisor of
0 - The result of every operation is between
-1015and1015
Clarifying questions
What you would ask an interviewer before writing any code.