204. Basic Calculator
Your function receives a string s holding a valid arithmetic expression built from non-negative integers, +, -, parentheses, and spaces, and must return the integer the expression evaluates to.
A - may also act as a unary sign directly in front of a number or an opening parenthesis (as in -(2 + 3)); + is always binary. There is no multiplication or division, so evaluation is strictly left to right, but parentheses can nest.
Calling your language's built-in expression evaluator (like Python's eval) is off the table — write the parser yourself, in one pass over the string.
Example 1:
Input: s = "1 + 1"
Output: 2
Explanation: A single addition; the spaces are ignored.
Example 2:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
Explanation: The inner group is 4+5+2 = 11, so the first parenthesis is 1+11−3 = 9, and 9 + 14 = 23.
Example 3:
Input: s = "-(2 + 3) - (-4)"
Output: -1
Explanation: The leading minus negates the whole group: −5. Subtracting −4 adds 4, giving −1.
Constraints:
- 1 ≤ s.length ≤ 3 * 10⁴
- s consists of digits, '+', '-', '(', ')', and ' '
- s is a valid expression; every number fits in a 32-bit signed integer, and so does the final result
- '-' may be unary (before a number or '('); '+' is never unary
Hints:
With only + and −, there is no precedence to worry about — a running total plus a pending sign (+1 or −1) evaluates any flat expression in one pass. Build multi-digit numbers as you scan: num = num * 10 + digit.
Parentheses are the only interruption. When you hit '(', you need to remember where you were — the total so far and the sign that was waiting to apply to the whole group.
Push (total, sign) onto a stack at every '(' and start fresh at 0. At ')', finish the inner total, then pop: total = popped_total + popped_sign * inner. Unary minus costs nothing extra — the pending sign was already −1 when the '(' arrived.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "1 + 1"
Expected output: 2