Basic Calculator

Problem

Implement a function that evaluates an arithmetic expression given as a string and returns its integer value. The expression contains non-negative integers, the operators + and -, parentheses ( and ), and spaces. A - may appear directly after ( or at the very start, meaning unary negation. You may not use any built-in expression evaluator such as eval.

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

Examples

• s = "7 - 12" → -5. Results may be negative.
• s = " 40 - 8 + 3 " → 35. Spaces anywhere are ignored, and - 8 + 3 is applied left to right.
• s = "(9-(2+3+1)+7)-(5-15)" → 20. The inner groups evaluate to 6 and -10, giving (9-6+7) - (-10).
• s = "-(4 - 11)" → 7. A minus in front of a parenthesised group flips the sign of everything inside.

Hints

1. With only + and -, you can keep a running total and a "current sign". What breaks that when you hit a (?
2. Whatever you had accumulated before the ( must be paused and resumed at the matching ). Paused state that resumes in reverse order lives on a stack.
3. Push (result, sign) on (, reset, and on ) pop and combine: result = saved_result + saved_sign * inner_result.