Calculate in postfix order
Evaluate an expression written with the operator after its two numbers, using a stack that holds the numbers waiting for an operator. About 14 minutes.
Operators come after their numbers
In postfix, 2 plus 1 is written 2 1 plus. And 2 plus 1, all times 3, is written 2 1 plus 3 times. There are no brackets, and no rule about which operator comes first. The order of the tokens already tells you.
Read the tokens from the left. A number is pushed onto the stack. An operator takes the two numbers on top, combines them, and pushes the result back.
stack = [2, 3] b = stack.pop() a = stack.pop() stack.append(a + b) # 5
Push 5. Stack: 5.
Mind the order and the division
The first number you pop is the right-hand side of the operator and the second is the left-hand side. For subtraction and division the order matters: 5 3 minus is 2, not minus 2.
Division in this task throws away the fractional part, rounding toward zero, so minus 7 divided by 2 is minus 3. In Python, plain integer division rounds down, so handle the sign yourself. At the end the stack holds exactly one number: the answer.
b = stack.pop() # second operand a = stack.pop() # first operand result = a - b
The tokens are 5, 3, minus. What is the result?
- A2
- B-2
- C8
Show the answer
2. The left side is 5 and the right side is 3, so 5 minus 3 is 2.
Evaluate reverse Polish notation
You are given an array of strings tokens that is an arithmetic expression in postfix order (reverse Polish notation). The operators are +, -, * and /, and every operand is an integer. Division truncates toward zero. Return the value of the expression. The expression is always valid, never divides by zero, and every intermediate result fits in a 32-bit integer.
tokens = ["2", "1", "+", "3", "*"] → 9
1 ≤ length of tokens ≤ 10,000 · each token is an operator or an integer in the range -200 to 200