Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Evaluate a string with '+', '-', parentheses, and non-negative integers in a single left-to-right pass. Keep a running `result`, the current `number` being built digit by digit, and the current `sign` (+1 or −1). On '+' or '-', fold `sign * number` into `result` and set the next sign. On '(', push the current `result` and `sign` onto a stack and reset both — you're starting a fresh sub-expression. On ')', fold the last number, then multiply by the sign that preceded the '(' and add back the saved outer result. No operator precedence to worry about since there's no '*' or '/'. O(n) time, O(n) space for the parenthesis stack.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can evaluate an expression in one pass without building an AST, correctly handling multi-digit numbers, the running sign, and saving/restoring context across nested parentheses.
Where candidates slip
Applying the sign to a single character instead of the full number, pushing/popping result and sign in the wrong order around parentheses, or forgetting to add the trailing number after the loop (and forgetting to skip spaces).
How to stand out
Explain that with only + and − there's no precedence, so the stack only needs to snapshot (result, sign) at each '(' and restore it at ')'. Then note the clean upgrade path to Basic Calculator II (add a number stack for * and /).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewread char cc is...?digit'+' / '-'Explore the full treeCollapse the tree
How to read it:Digits build the number; operators fold it; parentheses save/restore context.
How to read it:Each '(' pushes (result, sign); each ')' pops them to fold the inner value back in.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Single Pass — Running Result, Sign, and a Context Stack (Optimal)
1Hint 1Explore hintHide hint
There's no '*' or '/', so every operator has equal precedence and you can evaluate strictly left to right. What three running values do you need: the total so far, the number you're currently reading, and...?
2Hint 2Explore hintHide hint
Keep a sign (+1 or -1). When you hit '+' or '-', fold the current number into the result using the sign you had, then update the sign for what comes next.
3Hint 3Explore hintHide hint
A '(' starts a fresh sub-expression that the outer sign will later multiply. Save the current result and sign on a stack, reset them, and on ')' restore: result = inner * savedSign + savedResult.
A · Core idea
The crucial observation is that this expression has no multiplication or division, so there is no operator precedence — + and - are evaluated strictly left to right. That means we don't need an abstract syntax tree or a two-stack shunting-yard; we need only a running accumulator. We maintain three variables: result (the sum so far at the current parenthesis level), number (the integer currently being read, possibly multi-digit), and sign (+1 or −1, the sign that applies to number).
Building numbers and folding them. Digits are accumulated with number = number * 10 + digit, because a number can span several characters ("42" is two chars). We don't add number into result immediately — we wait until we know the number is complete, which happens exactly when we hit the next operator (+/-) or a closing ). At that moment we execute the fold: result += sign * number, then reset number to 0 and set sign according to the operator just seen (+1 for +, −1 for -). This lazy fold is why unary minus 'just works': sign starts at +1, and a leading - flips it to −1 before any number is folded.
Why parentheses need a stack. A sub-expression in parentheses must be fully evaluated and then combined with whatever came before it, under whatever sign preceded the (. Consider "3-(2+1)": when we reach (, we've accumulated result = 3 and we have a pending sign = −1 (from the -). We can't keep using the same result while computing the inside, so we push the context: save result and sign on the stack, then reset result = 0 and sign = +1 to evaluate the inner expression cleanly. The stack is the only structure that can remember arbitrarily deep nesting — each level gets its own saved snapshot.
Restoring context on ')'. When we hit ), we first fold the last inner number (result += sign * number) so result now holds the inner expression's value, call it V. Then we pop the two saved values. The order matters: we pushed result first and sign second, so we pop sign first and result second. The combine step is result = V * poppedSign + poppedResult. The poppedSign distributes the outer sign across the entire parenthesised value (handling -(2+1) → −3), and adding poppedResult resumes the outer computation right where it paused. For "3-(2+1)": V = 3, poppedSign = −1, poppedResult = 3, giving 3*(−1) + 3 = 0. Correct.
The trailing fold. The last number in the string has no operator after it to trigger a fold, so after the loop ends we must do one final result += sign * number. Forgetting this drops the final operand — a very common bug. Spaces are simply skipped on sight. Put together, the algorithm is a single linear scan with O(1) work per character and a stack bounded by nesting depth.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "(1+(4+5+2)-3)+(6+8)"Interactive diagram
Folding -(3+4)
'('Unary minus is just sign=-1 saved across the parenthesis and applied on ')'.
23C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
With only + and -, 'evaluate an expression' reduces to 'fold a signed stream', and parentheses are just save/restore points for the (result, sign) context. Recognizing that precedence is absent is what frees you from the heavier two-stack machinery. The same context-snapshot trick scales: add a number stack and you get Basic Calculator II (with * and /), and a full operator stack gives Basic Calculator III.
ComplexityO(n) time, O(n) space — Each character is visited once and does O(1) work (digit accumulation, a fold, or a push/pop) → O(n) time. The stack holds two ints per open parenthesis, so its size is proportional to the maximum nesting depth, O(n) in the worst case → O(n) space.
E · Edge cases and pitfalls10s = "1" — No operators; loop builds number=1; trailing fold returns 1.Explore edge casesHide edge cases
Edge cases handled
s = "1"No operators; loop builds number=1; trailing fold returns 1.s = "-1"sign flips to -1, number=1; trailing fold → -1 (unary minus).s = "2-(5-6)"inner 5-6=-1; result = (-1)*(-1) + 2 = 3.s = " 30 "Spaces skipped; multi-digit number=30; returns 30.s = "(((1)))"Deep nesting; each ')' restores 1*1+0 → 1.
Pitfalls
- Applying the sign to a single digit instead of the full multi-digit number.
- Popping result and sign in the wrong order on ')' — they're symmetric to the push order.
- Forgetting the trailing 'result += sign * number' after the loop — drops the last operand.
- Not resetting number to 0 after folding — the next number gets contaminated.
- Forgetting to skip spaces or mis-handling them as operators.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int calculate(String s) { Deque<Integer> stack = new ArrayDeque<>(); int result = 0; // running total at the current level int number = 0; // number currently being built int sign = 1; // +1 or -1, applies to `number`Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Dropping the trailing number
The last operand has no operator after it to trigger the fold inside the loop, so it must be folded once more after the loop. Omitting this returns a result missing the final term.
Explore the code comparisonHide the code comparison
Dropping the trailing number
The last operand has no operator after it to trigger the fold inside the loop, so it must be folded once more after the loop. Omitting this returns a result missing the final term.
Don't write this
for c in s:
# ... folds happen on operators only ...
return result # last number never foldedWrite this instead
for c in s:
# ... folds happen on operators only ...
return result + sign * number # fold the trailing number2Wrong pop order on ')'
We push result then sign, so on ')' we must pop sign first (to multiply) and result second (to add). Swapping them adds the sign and multiplies by the outer result — nonsense.
Explore the code comparisonHide the code comparison
Wrong pop order on ')'
We push result then sign, so on ')' we must pop sign first (to multiply) and result second (to add). Swapping them adds the sign and multiplies by the outer result — nonsense.
Don't write this
result += sign * number;
result += stack.pop(); // popped sign, added it
result *= stack.pop(); // popped result, multiplied by itWrite this instead
result += sign * number;
result *= stack.pop(); // sign before '('
result += stack.pop(); // result before '('3Applying the sign to a single digit
Numbers can be multi-digit. Folding on every digit (rather than when the number completes) computes garbage like treating '42' as 4 then 2.
Explore the code comparisonHide the code comparison
Applying the sign to a single digit
Numbers can be multi-digit. Folding on every digit (rather than when the number completes) computes garbage like treating '42' as 4 then 2.
Don't write this
if c.isdigit():
result += sign * int(c) # folds each digit separatelyWrite this instead
if c.isdigit():
number = number * 10 + int(c) # build the full number, fold laterRevise
Carry the pattern into the interview
Pattern to remember
Single pass with running result + sign; stack saves context across '( )'
Code pattern to memorize
result=0; number=0; sign=1; stack=[]
for c in s:
if c.isdigit(): number = number*10 + int(c)
elif c=='+': result += sign*number; number=0; sign=1
elif c=='-': result += sign*number; number=0; sign=-1
elif c=='(': stack.push(result); stack.push(sign); result=0; sign=1
elif c==')':
result += sign*number; number=0
result *= stack.pop() # sign before '('
result += stack.pop() # result before '('
return result + sign*numberRules to remember
- 1Build multi-digit numbers with
number = number*10 + digit— a single char is never a full number. - 2Apply the pending
sign * numberintoresultwhen you hit the next operator or ')', not eagerly. - 3On
'(', pushresultthensign, and reset both — the sub-expression starts clean. Pop in the reverse order on')'. - 4On
')', first fold the last number, thenresult = result * savedSign + savedResult— the sign distributes over the whole parenthesised value. - 5After the loop, add the trailing
sign * number— the last number has no operator after it to trigger the fold. Skip spaces.
Use this pattern when
- Evaluate an arithmetic expression with + / − and nested parentheses
- Any parse where a context (sign, scale) must be saved/restored across brackets
- Folding a token stream into a running accumulator with a sign flag
- Expression problems without operator precedence (only + and −)
Choose another pattern when
- Expression has '*' and '/' too → precedence matters; use the two-stack or 'last term on a stack' method (Basic Calculator II)
- Full precedence + parentheses + unary → shunting-yard / AST is cleaner (Basic Calculator III)
- You need the parse tree, not just the value → build an AST explicitly
- Reverse Polish / postfix input → simpler single operand stack (Evaluate RPN)
Interview takeaway
When the only operators are + and −, you don't need operator precedence — you need to remember the SIGN and the partial RESULT each time you enter a parenthesis, and restore them on exit. A stack of (result, sign) snapshots is the whole trick, and it generalizes directly to the precedence-aware Basic Calculator II/III.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSingle-pass expression evaluation with a context stack. Recognize it when an expression has only + and − (no precedence) but has parentheses: track a running result and sign, and snapshot (result, sign) on '(' to restore on ')'. The save/restore-on-bracket idea is the same as Decode String, and the term-stack extension yields Basic Calculator II/III.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Basic Calculator IIComing soonAdds '*' and '/' (no parentheses). Use a number stack: push terms, but pop-and-combine on '*'/'/' for precedence.
- Basic Calculator IIIComing soonFull precedence WITH parentheses — combine the stack-of-context idea with the term stack, or recurse on parentheses.
- Evaluate Reverse Polish NotationPostfix input — a single operand stack, no precedence parsing needed.
- Decode StringComing soonSame save/restore-context-on-bracket pattern; the stack holds (string, count) instead of (result, sign).