Evaluate a string expression with numbers, plus, minus, brackets and spaces. No multiplication or division, and you cannot use a built-in evaluator.
DSA Animator › DSA Revision › Stack › Basic Calculator
Remember: with only plus and minus, keep a result and a sign. Brackets save and restore that state with a stack. The video solves Basic Calculator (LeetCode 224, Hard) with the Stack pattern from the Stack topic, and you can replay every step in the interactive Basic Calculator animation.
Evaluate a string expression with numbers, plus, minus, brackets and spaces. No multiplication or division, and you cannot use a built-in evaluator.
1 minus, open bracket, 2 plus 3, close bracket, plus 4 equals 0.
Converting to postfix first works, but it is more machinery than needed. With only plus and minus, a running result and a sign are enough, plus a stack for brackets.
Keep a running result and the sign of the next number. On an opening bracket, push the current result and sign, and start a fresh result inside. On a closing bracket, finish the inner result, then pop: the outer result plus the sign times the inner result.
Read 1, then minus: the result is 1, and the next sign is minus. Open bracket: push 1 and minus, and start fresh. Inside, 2 plus 3 gives 5. Close bracket: pop, and the result becomes 1 minus 5, which is minus 4. Then plus 4 gives 0.
In code, build multi-digit numbers digit by digit. On plus or minus, add sign times number to the result, reset the number, and set the new sign. On an opening bracket, push result and sign, then reset both; on a closing bracket, combine with the popped values. Each character is handled once, so it's O of n time and O of n space.
Remember: with only plus and minus, keep a result and a sign. Brackets save and restore that state with a stack.