Calculator without brackets

Problem

Evaluate an arithmetic line with non-negative integers and the operators + - * /. Multiplication and division happen before addition and subtraction. Division truncates toward zero. Spaces may appear anywhere between tokens. The divisor is never zero.

Input, output and limits

Input: One line with the expression.
Output: One integer.
Constraints: 1 ≤ length ≤ 100000
All values fit in 64 bits

Examples

Example 1

Input

2+3*4

Output

Multiply first: 2 + 12 = 14.

Example 2

Input

 14 - 6 / 4

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

Keep a stack of terms. Remember the operator that came before the current number.

Hint 2

+ pushes the number, - pushes its negative, * and / change the top term.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Queue built from two stacksmedium
Smallest number after removing digitshard
Elimination circlemedium
Decode a repeated stringhard
Stack with minimummedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Stacks & Queues problems

Problem

Input, output and limits

Examples

Hints

More Stacks & Queues problems