499. Basic Calculator III
You are given a string expression holding a valid arithmetic expression built from non-negative integers, the four operators +, -, *, /, parentheses, and optional spaces. Evaluate it and return its value as an integer.
The usual rules apply: * and / bind tighter than + and -, parentheses override everything, and operators of equal precedence are evaluated left to right. Division is integer division truncating toward zero, so (1-6)/4 evaluates to -1, not -2.
No unary operators appear (every +/- sits between two operands), and you may not lean on eval-style library helpers — build the evaluator yourself.
Example 1:
Input: expression = "1+1"
Output: 2
Explanation: A single addition: 1 + 1 = 2.
Example 2:
Input: expression = "2*(5+5*2)/3+(6/2+8)"
Output: 21
Explanation: Inside the first group 5 + 5*2 = 15, so 2*15/3 = 10 (left to right). The second group is 6/2 + 8 = 11. Total 10 + 11 = 21.
Example 3:
Input: expression = "6-4/2"
Output: 4
Explanation: Division binds tighter than subtraction: 6 - (4/2) = 6 - 2 = 4.
Constraints:
- 1 ≤ expression.length ≤ 10⁴
- expression contains only digits, '+', '-', '*', '/', '(', ')', and spaces
- expression is a valid expression; every operator is binary (no unary + or -)
- No division by zero occurs
- Every intermediate value fits in a signed 64-bit integer
Hints:
Think of any (sub)expression as a **sum of signed terms**: 6-4/2 is (+6) + (-(4/2)). Additions and subtractions can wait until the end, but * and / must be applied immediately — they combine only with the term directly to their left.
Keep a list of finished signed terms, the number being read, and the operator waiting to its left. On + or -, push the number with its sign; on * or /, pop the last term, combine, push back.
Parentheses are just nesting: on '(' save the outer (terms, pending operator) on a stack and start fresh; on ')' collapse the inner terms to one value and treat it exactly like a number you just read. Alternatively, write a recursive-descent parser: expression → terms, term → factors, factor → number or (expression).
Watch division on negative intermediates: the answer truncates toward zero, but Python's // floors, so (1-6)/4 must give -1, not -2.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: expression = "1+1"
Expected output: 2