Basic Calculator
Implement a basic calculator to evaluate a string expression s containing +, -, (, ), non-negative integers, and spaces.
Intuition
Without parentheses, evaluating + and - left to right is trivial — walk through, accumulate a running total, flipping the sign when you see -. Parentheses complicate this because they group a sub-expression whose result is added or subtracted depending on the sign before the parenthesis. A stack handles this naturally: when you hit (, push the current result and the current sign onto the stack, reset, and evaluate the sub-expression. When you hit ), pop the saved sign and result, and combine. The stack depth equals the nesting level.
When you see an expression evaluation problem with parentheses, the pattern is a stack that saves and restores context at each nesting level. The operators here (+, -) have equal precedence, so there is no operator-precedence stack — just result-and-sign stacking for parentheses. If * and / were involved, you would need a different approach (see Basic Calculator II).
Approach
Walk character by character, building multi-digit numbers
Iterate through the string. When you encounter a digit, accumulate it into a num variable (num = num * 10 + int(ch)). When you encounter a non-digit (or reach the end), the number is complete — apply it to the running total using the current sign.
Track the current sign and apply it on each number
Maintain a sign variable (1 or -1). On +, set sign = 1; on -, set sign = -1. When a number completes, add sign * num to the running result. This handles a sequence like 3 - 2 + 1 correctly.
Use a stack to handle parentheses as nested sub-expressions
On (: push the current result and sign onto the stack, then reset result = 0 and sign = 1 to begin evaluating the sub-expression fresh. On ): the sub-expression's result is now in result. Pop the saved sign and previous result, and compute prev_result + saved_sign * result. This correctly handles nesting: 1 - (2 - (3 + 4)) evaluates the innermost group first.
Solution
Common pitfalls
Forgetting to process the last number at the end of the string
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '+':
result += sign * num
num = 0
sign = 1for i, ch in enumerate(s):
...
result += sign * numThe last number in the string has no trailing operator to trigger its processing. Without the final result += sign * num after the loop, the last number is silently dropped.
Not resetting result and sign when entering a parenthesized group
if ch == '(':
stack.append(result)if ch == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1The parenthesized sub-expression must be evaluated from scratch. Without resetting, you accumulate its terms into the outer result, ignoring grouping entirely.
Applying the saved sign to the wrong operand on )
result = stack.pop() + result
result = stack.pop() * result + stack.pop()
The stack has [prev_result, saved_sign] (sign pushed last). You must pop the sign first and multiply it by the sub-expression result, then add the previous result. Skipping the sign makes 1 - (3) evaluate to 1 + 3 = 4 instead of -2.
Edge cases
-1 + 2The initial sign = 1 and result = 0 mean that - sets sign = -1, and the first number is correctly subtracted from 0.
1 - (2 - (3))Each ( pushes to the stack. The innermost expression evaluates to 3, which the middle expression subtracts: 2 - 3 = -1. Then the outer expression: 1 - (-1) = 2.
Spaces are simply skipped. They do not terminate a number — only a non-digit, non-space character does (or the end of the string).