Challenge: Postfix Calculator

Lab Python Intermediate 20 points

In postfix notation the operator comes after its two numbers: 3 4 + means 3 + 4, and 5 1 2 + 4 * + 3 - means 5 + (1 + 2) × 4 − 3. Evaluate a postfix expression with a stack. Division / is whole-number division (round down, like //).

Input

One line: numbers and operators + - * / separated by spaces.

Output

The result.

Example

Input

3 4 +

Output

Sample input available Sample output available

Editor

Python

Hints

Numbers go on the stack.

For an operator, pop b first, then a, and push a (op) b.

Solution explanation

Order matters for − and /: the first number popped is the right side.

Show solution

stack = []
for tok in input().split():
    if tok in "+-*/":
        b = stack.pop()
        a = stack.pop()
        if tok == "+":
            stack.append(a + b)
        elif tok == "-":
            stack.append(a - b)
        elif tok == "*":
            stack.append(a * b)
        else:
            stack.append(a // b)
    else:
        stack.append(int(tok))
print(stack[0])

Output

Answer