hardStack / QueuePure DSA~45 min
Expression Evaluator With Parentheses
A config system lets operators write arithmetic guards like '(2 + 3) - (4 - (1 + 1))'. Evaluate such an expression containing non-negative integers, '+', '-', parentheses, and spaces.
Problem
Implement a calculator that evaluates a string expression containing digits, '+', '-', '(', ')', and spaces. There is no multiplication or division and no unary minus beyond what parentheses imply. Return the integer result.
Input
A string s (1 ≤ |s| ≤ 3·10^5) of a valid expression.
Output
An integer: the evaluated result.
Constraints
- Operators are binary '+' and '-' only
- Parentheses may nest arbitrarily
- The expression is always valid
Examples
Example 1
Input
s = "(1+(4+5+2)-3)+(6+8)"
Output
23
Inner groups evaluate to 9 then the whole expression to 23.
Example 2
Input
s = " 2-1 + 2 "
Output
3
Spaces are ignored; left-to-right gives 3.