The problem
Evaluate a string containing +, −, parentheses, and non-negative integers (unary minus allowed via parentheses).
Stuck? Reveal hints one at a time
How to approach it
- 1Variables: result, sign (+1/−1), currentNumber; a stack for suspended contexts.
- 2Digit → build number. + / − → fold number into result with the pending sign, set the new sign.
- 3"(" → push result and sign, reset result = 0, sign = 1.
- 4")" → fold the pending number, then result = poppedResult + poppedSign × result.
- 5Fold once more at the end.
Key insight
Parentheses are recursion; the (result, sign) pair is the entire stack frame needed to resume the outer expression — the same trick as Decode String.
The solution
Watch out for
- The final "+ sign * num" outside the loop catches expressions not ending in ")".
- Push order and pop order must mirror each other — pop sign first if you pushed it last.