visual walkthrough
Basic Calculator
Signs and nested parentheses with a stack; asked at Google and Meta.
The idea
Without multiplication, an expression is just a running total with signs. Brackets are the only complication: a minus before a bracket flips everything inside.
So when a bracket opens, save the total so far and the sign in front of it. When it closes, combine: saved total + saved sign × (value inside).
Complexity
| approach | time | space |
|---|---|---|
| Recursion on brackets | O(n²) worst case | O(n) |
| One pass with a sign stack | O(n) | O(n) |