Basic Calculator II

Problem

Evaluate an arithmetic expression given as a string s and return its integer value. The string contains non-negative integers, the operators +, -, *, /, and spaces. There are no parentheses. Operators follow the usual precedence (* and / before + and -, all left-associative), and integer division truncates toward zero. Do not use a built-in evaluator.

• The string has between 1 and 400,000 characters.
• The expression is valid and every intermediate value fits in a signed 32-bit integer.
• There is no division by zero.

Examples

• s = "9+4*3" → 21. Multiplication binds tighter, so it is 9 + 12.
• s = " 17/5 " → 3. Integer division truncates, and surrounding spaces are ignored.
• s = " 6+11 / 4 " → 8. 11 / 4 is 2, then 6 + 2.
• s = "20-7/2" → 17. 7 / 2 is 3, so 20 - 3.

Hints

1. + and - can be applied left to right, but * and / must combine with the number immediately before them. What do you need to remember about that number?
2. Think of the expression as a sum of signed terms, where each term is a chain of multiplications and divisions.
3. Keep a stack of completed terms. When you see * or /, pop the last term, combine it with the new number, and push it back. The answer is the sum of the stack.