Evaluate Postfix Tokens
Problem
A pocket calculator stores formulas in postfix order, where each operator comes after its two operands, so "3 4 +" means 3 + 4 and no brackets are ever needed. Given the formula as a list of tokens, each an integer or one of +, -, * and /, return its value. Division truncates toward zero, so 7 / -2 is -3. The formula is always valid, has between 1 and 10,000 tokens, never divides by zero, and every intermediate value fits in a 32-bit signed integer.
Examples
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Why: (2 + 1) * 3Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Why: 4 + (13 / 5), and 13 / 5 truncates to 2Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Why: negative numbers such as -11 are operands, not operatorsHints
0 / 3
When an operator arrives, its operands are the two most recent values that have not been used yet.
Push numbers onto a stack. On an operator, pop the right operand first and then the left one, apply the operator and push the result back.
Order matters for - and /. Python's // rounds toward minus infinity, so divide the absolute values and put the sign back yourself to truncate toward zero.
Solution
In postfix order an operator always applies to the two most recent unused values, which is exactly what the top of a stack holds. Numbers are pushed; an operator pops the right operand, then the left one, and pushes the combined value, so at the end the only value left is the answer. The one trap is division: Python's floor division rounds -7 // 2 down to -4, so the quotient is taken on absolute values and its sign restored, which truncates toward zero. A token is an operator only if it is exactly one of the four symbols, so "-11" is read as a number. Time and space are both O(n).
def eval_postfix(tokens):
stack = []
for tok in tokens:
if tok not in ("+", "-", "*", "/"):
stack.append(int(tok))
continue
right, left = stack.pop(), stack.pop() # right operand is on top
if tok == "+":
stack.append(left + right)
elif tok == "-":
stack.append(left - right)
elif tok == "*":
stack.append(left * right)
else:
q = abs(left) // abs(right) # truncate toward zero
stack.append(q if (left < 0) == (right < 0) else -q)
return stack[0]
print(eval_postfix(["2", "1", "+", "3", "*"])) # -> 9
print(eval_postfix(["4", "13", "5", "/", "+"])) # -> 6
print(eval_postfix(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) # -> 22Stuck on the idea rather than the code? Stack Basics covers it.