Work out a calculation written with the operators after their numbers.
What to build
The classic use of a stack in calculators and compilers.
Requirements
- Read a line of tokens separated by spaces. Each is a whole number or one of
+,-and*. - Evaluate it with a stack and print the result.
- Print
errorif an operator has too few values, or if more than one value is left at the end.
Input
One line.
Output
One line.
Constraints
There are from 1 to 200 tokens. Numbers are from 0 to 1000.
Example
Input:
3 4 + 2 *
Output:
14
Why it works
Each operator applies to the two most recent values, so a stack always has them on top. No brackets or precedence rules are needed.
Examples
Example 1 · Input
3 4 + 2 *
Expected output
14
Example 2 · Input
5 1 2 + 4 * + 3 -
Expected output
14
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Numbers go onto a stack.
Hint 2
An operator pops two values. The first popped is the right-hand value.
Hint 3
At the end, exactly one value should be left.
Solution
Show one correct solution (try it yourself first)
def evaluate(tokens):
stack = []
for token in tokens:
if token in "+-*":
if len(stack) < 2:
return "error"
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
else:
stack.append(left * right)
else:
stack.append(int(token))
return stack[0] if len(stack) == 1 else "error"
print(evaluate(input().split()))