207. Basic Calculator II
You are given a string s containing a valid arithmetic expression built from non-negative integer literals and the four operators +, -, *, and /. Spaces may appear anywhere between tokens. Evaluate the expression and return its value as an integer.
The usual precedence rules apply: * and / bind tighter than + and -, and operators of the same precedence are applied left to right. Division is integer division that truncates toward zero — so 14 / 4 is 3, and if a negative value ever meets a division it rounds toward zero, not down.
You may not call a built-in expression evaluator such as eval.
Example 1:
Input: s = "3+2*2"
Output: 7
Explanation: The multiplication happens first: 2 * 2 = 4, then 3 + 4 = 7.
Example 2:
Input: s = " 3/2 "
Output: 1
Explanation: 3 / 2 truncates to 1. Surrounding spaces are ignored.
Example 3:
Input: s = " 3+5 / 2 "
Output: 5
Explanation: 5 / 2 truncates to 2 first, then 3 + 2 = 5.
Constraints:
- 1 ≤ s.length ≤ 3 * 10⁵
- s consists of digits, '+', '-', '*', '/', and spaces
- s is a valid expression; every '-' is binary (there are no negative literals)
- Every number and every intermediate result fits in a signed 32-bit integer
- Division never divides by zero
Hints:
You never need parentheses here, so precedence is the whole puzzle: a `*` or `/` must be applied to its left neighbor immediately, while a `+` or `-` can wait until the very end.
Scan once, keeping a stack of signed terms. On '+', push the number; on '-', push its negation; on '*' or '/', pop the top, combine it with the number, and push the result. The answer is the sum of the stack.
Once the stack idea works, notice you only ever touch its top — replace the stack with two variables: a running total of finished terms and the current term being multiplied/divided.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "3+2*2"
Expected output: 7