Basic Calculator
Implement a basic calculator to evaluate a string expression s containing +, -, (, ), non-negative integers, and spaces.
- 1 <= s.length <= 3 * 10⁵
- s consists of digits, '+', '-', '(', ')', and ' '.
- s represents a valid expression.
- '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
- '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
- There will be no two consecutive operators in the input.
- Every number and running calculation will fit in a signed 32-bit integer.
Intuition
This is basic calculator leetcode problem 224: evaluate a string expression containing +, -, parentheses, and non-negative integers. There is no multiplication or division, which removes precedence entirely — the only difficulty is the nesting.
A natural instinct is to recurse on each parenthesis. That works, but a single left-to-right scan with a stack is simpler and avoids the recursion depth.
The reframing that makes it easy is to treat every number as signed and just keep adding. Then 1 - 2 is 1 + (-2), and there is no subtraction to handle separately — only a running sign that flips when a - is read:
- Maintain a running result and a current sign; each number is added as sign × number, so subtraction disappears entirely.
Parentheses are handled by saving state rather than recursing. On (, push the result so far and the sign that applies to the whole group, then reset both to start the inner expression fresh. On ), the inner result is finished — multiply it by the saved sign and add the saved result back.
The critical ordering detail is that the sign pushed at ( is the sign before the parenthesis, which applies to the entire group. In 5 - (3 + 2), that saved -1 is what turns the inner 5 into -5.
Multi-digit numbers must be accumulated across characters with num = num * 10 + digit, and spaces skipped. A number is only committed when a non-digit is reached — and the final number needs committing after the loop ends, since no operator follows it.
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
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) time and O(n) space.
Treat every number as signed
Keep a running result and a current sign, adding sign * number each time. Subtraction disappears — 1 - 2 is just 1 + (-2) — which removes an entire branch.
Accumulate multi-digit numbers
Build digits with num = num * 10 + digit while characters remain numeric, and skip spaces. A number is committed only when a non-digit is reached.
Push state on an open parenthesis
Push the result so far and the sign applying to the whole group, then reset both. The pushed sign is the one before the parenthesis — in 5 - (3 + 2) that saved -1 negates the entire inner result.
Restore state on a close parenthesis
The inner expression is complete: multiply it by the saved sign and add the saved result back. The outer computation then continues as if the group were a single number.
Update the sign on operators
A + sets the sign to 1 and a - sets it to -1, applying to the next number read. No operator precedence exists here, since there is no multiplication or division.
Commit the final number
Add the last number after the loop ends. No operator or parenthesis follows it, so nothing inside the loop triggers its commit — a common cause of an answer short by the last term.
Cost of the scan
Each character is examined once, giving O(n) time. Space is O(n) for the stack in the worst case of deeply nested parentheses.
Solution & live demo
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).