← DSA Atlas
Dedicated problem page · #224

Basic Calculator

HardStack and Expression ProcessingStack for parenthesized sign contextStack
Solve on LeetCode ↗
224
HardStack and Expression ProcessingStackStack for parenthesized sign context

Basic Calculator

Implement a basic calculator that evaluates a string expression containing non-negative integers, '+', '-', '(', ')' and spaces. There is no multiplication or division. Return the integer result. You must handle nested parentheses and unary-like leading signs correctly, without using a built-in eval.

Open official problem prompt ↗
In plain English

Evaluate an expression with plus, minus, and arbitrarily nested parentheses to a single integer.

Picture it like this

Doing running arithmetic on paper, but each time you open a bracket you jot down the total and the +/- sitting in front of it on a shelf, then start fresh; closing the bracket takes them back off the shelf.

Example
Input
s = "1-(2+3)"
Output
-4
Why
The parentheses evaluate to 2+3 = 5, and 1 - 5 = -4.
Constraints
1 <= s.length <= 3 * 10^5s consists of digits, '+', '-', '(', ')' and ' 's is a valid expressionThe final result and all intermediate values fit in a 32-bit signed integer
Pattern lesson

See the pattern, then code

Stack for parenthesized sign context
Recognition clue

Parentheses that flip and restore the surrounding sign context are the signal to stack the running result and sign at each '(' and pop them at ')'.

↗
Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. Track a running result and the current sign. A '(' opens a new sub-expression, so save the outer result and sign, then reset. A ')' finishes the sub-expression and folds it back into the saved outer state.

New words, made simpleKnow these before the algorithm
Running result
The accumulated value of everything evaluated at the current nesting level.
Sign context
Whether the next number should be added or subtracted, tracked as +1 or -1.
Sub-expression
The portion inside a matching pair of parentheses, evaluated independently then folded in.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Recursive descent parser

Correct but heavier; recursion depth mirrors nesting and needs careful index sharing.

Recurse on '(' and return at ')', evaluating each level in its own call.

Time O(n)Space O(n)
Best choiceSingle stack of result and sign

One iterative pass with minimal state; the standard clean solution.

Push the outer result and sign at '(', reset, and fold back at ')'.

Time O(n)Space O(n)
The rule we keep true

Invariant

At any point, result holds the value of the current parenthesis level for everything before the pending number, and sign is the operator waiting to apply to that pending number.

Why this is correct

Reasoning

There is no precedence to resolve beyond parentheses, so left-to-right accumulation with a sign is exact. Pushing result and sign at '(' preserves the entire outer context; on ')' the finished inner value is multiplied by the saved sign (the operator that preceded the '(') and added to the saved outer result, precisely reconstructing what left-to-right evaluation would have produced.

The algorithm in three movesSay these aloud before coding
1Maintain result, current number, and current sign (+1/-1)

'1','-': result=1, sign=-1

2On a digit build the number; on '+'/'-' add sign*number to result and set the new sign

'(': push 1, push -1; result=0, sign=1

3On '(' push result then sign, and reset result to 0 and sign to +1

'2','+','3',')': inner=5

4On ')' fold in the last number, multiply by the popped sign, and add the popped outer result

result = 5*(-1)+1 = -4

5After the scan add the final sign*number

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
-1
(2
23
+4
35
)6
1 · Read'1'
2 · AskBuild number
3 · Update statenum=1, result=0, sign=1
4 · Resultnum becomes 1
Key takeaway

The '(' saves the outer result and sign; the ')' multiplies the inner value by that saved sign and adds the outer result.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 8-9Accumulate multi-digit numbers

    Digits are folded into num so numbers longer than one character parse correctly.

  2. 2
    Lines 10-16Commit on operators

    Each '+'/'-' pushes the finished number into result and records the sign for the next number.

  3. 3
    Lines 17-21Open parenthesis

    Save the outer result and sign on the stack, then reset to evaluate the inside from scratch.

  4. 4
    Lines 22-26Close parenthesis

    Finish the inner number, scale the inner result by the saved sign, and add back the saved outer result.

  5. 5
    Lines 27Flush the tail

    The last number after the final operator has not been committed yet, so add it before returning.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Leading negative like '-1' or a sign right after '('
  • Spaces scattered anywhere in the string
  • Deeply nested parentheses
  • Multi-digit numbers
  • A number with no trailing operator at the very end
!

Common beginner mistakes

  • Forgetting the final result + sign*num for the last number
  • Pushing sign and result in the wrong order so they pop swapped
  • Only handling single-digit numbers
  • Not resetting num to 0 after committing it
  • Assuming precedence exists (there is no '*' or '/' here, so none is needed)
Check your understanding

When you hit ')', why multiply the inner result by the popped sign before adding the popped outer result?

More in Stack and Expression Processing

#20Valid ParenthesesMatching stack for bracket pairs#71Simplify PathStack of path components#150Evaluate Reverse Polish NotationOperand stack for postfix evaluation#155Min StackStack augmented with running minimum#227Basic Calculator IIStack with deferred multiply/divide#394Decode StringNested-context stack