Solving tips
- Key insight: with only + and -, there is no precedence, just carry a running result and a current sign (+1/-1); subtraction is adding sign*-1.
- On '(' push (result, sign) and reset both; on ')' flush the inner number then combine result = prev_result + prev_sign * inner.
- Target O(n) time and O(n) space; prefer the explicit iterative stack over recursion since deep nesting can exceed the recursion limit at n up to 3e5.
- Common pitfalls: accumulate multi-digit numbers with num=num*10+digit, do the final result+sign*num flush after the loop, and push the sign (not just result) at '(' so -(1+2) negates correctly.
Problem
Evaluate an arithmetic expression given as a string s and return its value as an integer.
The expression may contain:
- non-negative integer literals (possibly multi-digit),
- binary
+ and -,
- unary
- (and unary +), e.g. "-2+1" or "-(3+4)",
- parentheses
( ),
- spaces, which are meaningless.
There is no multiplication or division, the expression is always valid, and no intermediate value overflows a 64-bit integer. You may not use eval() or any built-in expression evaluator.
Examples
Example 1
Input: s = "1 + 1"
Output: 2
Explanation: spaces are ignored; simple addition.
Example 2
Input: s = " 2-1 + 2 "
Output: 3
Explanation: left-to-right evaluation, 2 - 1 = 1, then 1 + 2 = 3.
Example 3
Input: s = "-(5 - (1 + 2))"
Output: -2
Explanation: the inner sum is 3, 5 - 3 = 2, and the leading unary minus negates it.
Constraints
1 <= s.length <= 3 * 10^5s consists of digits, +, -, (, ), and ' '.- The length bound demands a single O(n) pass — re-evaluating innermost parentheses repeatedly is too slow.
Think about it first
Hint 1
With only + and −, every term is just added — a `-` is the same as adding the next value multiplied by −1. Can you carry a "current sign" instead of doing subtraction?
Hint 2
The only real difficulty is parentheses: `-(...)` must negate everything inside. What do you need to remember when you enter a `(` so you can resume correctly at the matching `)`?
Hint 3
Keep a running `result` and a `sign` (+1/−1). On `(`, push both onto a stack and reset them; on `)`, finish the inner result, pop, and combine: `result = popped_result + popped_sign * inner`.
TL;DR
One pass with a running sign and a stack that saves (result, sign) at every ( — O(n) time, O(n) space.
Approach 1 — Brute force (collapse innermost parentheses)
Since only + and - exist, a parenthesis-free expression is easy to evaluate. So: repeatedly find an innermost (...) pair (the last ( before the first )), evaluate that flat piece, and splice its value back into the string until no parentheses remain.
class Solution:
def calculate(self, s: str) -> int:
def eval_flat(expr: str) -> int:
result = 0
sign = 1
i, n = 0, len(expr)
while i < n:
c = expr[i]
if c.isdigit():
num = 0
while i < n and expr[i].isdigit():
num = num * 10 + int(expr[i])
i += 1
result += sign * num
sign = 1
continue
if c == "-":
sign = -sign # handles unary minus and spliced negatives
i += 1
return result
while ")" in s:
close = s.index(")")
open_ = s.rindex("(", 0, close)
inner = eval_flat(s[open_ + 1 : close])
s = s[:open_] + "+" + str(inner) + s[close + 1 :]
return eval_flat(s)
(Flipping sign on every - makes spliced values like +-3 evaluate correctly.)
Complexity: each of up to O(n) parenthesis pairs triggers an O(n) scan-and-rebuild → O(n²) time, O(n) space.
With n = 3 * 10^5 and deep nesting, that’s ~10^10 character touches — hopeless; the string surgery must go.
Approach 2 — One pass with a sign stack
The insight: with only +/-, subtraction is just addition with a coefficient of −1, so you never need operator precedence — only a current sign. The one thing a ( threatens is that sign context; so when you meet (, push the accumulated result and the sign that applies to the whole group, reset both, and on ) combine: result = saved_result + saved_sign * inner_result. The stack holds exactly one frame per unclosed parenthesis.
class Solution:
def calculate(self, s: str) -> int:
result = 0
sign = 1
num = 0
stack: list[int] = [] # frames of [.., result, sign]
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == "+":
result += sign * num
num, sign = 0, 1
elif ch == "-":
result += sign * num
num, sign = 0, -1
elif ch == "(":
stack.append(result)
stack.append(sign)
result, sign = 0, 1
elif ch == ")":
result += sign * num
num = 0
prev_sign = stack.pop()
prev_result = stack.pop()
result = prev_result + prev_sign * result
# spaces: ignore
return result + sign * num
Walkthrough of Example 3 — s = "-(5 - (1 + 2))":
| ch | action | result | sign | num | stack |
|---|
- | flush 0, set sign | 0 | −1 | 0 | |
( | push (0, −1), reset | 0 | +1 | 0 | 0, −1 |
5 | build num | 0 | +1 | 5 | 0, −1 |
- | flush: 0+1·5 | 5 | −1 | 0 | 0, −1 |
( | push (5, −1), reset | 0 | +1 | 0 | 0, −1, 5, −1 |
1 | build num | 0 | +1 | 1 | … |
+ | flush: 0+1·1 | 1 | +1 | 0 | … |
2 | build num | 1 | +1 | 2 | … |
) | flush → 3; combine 5 + (−1)·3 | 2 | +1 | 0 | 0, −1 |
) | flush → 2; combine 0 + (−1)·2 | −2 | +1 | 0 | |
Final: -2 + 1*0 = -2. Matches.
Complexity: O(n) time — each character is processed once, each ( pushes and each ) pops exactly one frame. O(n) space for the stack in the worst case ((((((...).
Approach 3 — Recursive descent
The insight: parentheses define a recursive grammar, so let the call stack be the stack. This is recursive-descent parsing — a top-down technique where each grammar rule becomes a function; here one function evaluates a +/- sequence and recurses when it meets (, returning both the value and the position where the caller should resume.
class Solution:
def calculate(self, s: str) -> int:
n = len(s)
def parse(i: int) -> tuple[int, int]:
result = 0
sign = 1
num = 0
while i < n:
ch = s[i]
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == "+":
result += sign * num
num, sign = 0, 1
elif ch == "-":
result += sign * num
num, sign = 0, -1
elif ch == "(":
num, i = parse(i + 1) # i lands on the matching ')'
elif ch == ")":
return result + sign * num, i
i += 1
return result + sign * num, i
value, _ = parse(0)
return value
Walkthrough of Example 3 — "-(5 - (1 + 2))": the outer call reads - (sign −1) and (, so it recurses at index 2. That call accumulates 5, sets sign −1, meets ( and recurses again; the innermost call computes 1 + 2 = 3 and returns at its ). The middle call treats 3 as its pending num, so at its ) it returns 5 + (−1)·3 = 2. Back at the top, 2 becomes num under sign −1, and the final flush yields 0 + (−1)·2 = −2.
Complexity: O(n) time, O(n) space for the recursion stack. Caveat: at n = 3 * 10^5, an input like "((((("… nests deeper than CPython’s default recursion limit (~1000), so the iterative Approach 2 is the safe submission; the recursive form is still worth knowing as the parsing-interview phrasing.
Common pitfalls
- Handling only single-digit numbers — accumulate
num = num * 10 + digit across consecutive digits.
- Forgetting the final
result + sign * num flush after the loop; expressions like "1 + 2" don’t end in ) so the last number is still pending.
- Missing unary minus:
- at the start or right after ( must work; it falls out naturally only because num starts at 0 (flushing sign * 0 is harmless).
- Pushing only
result (not sign) at ( — then -(1+2) wrongly evaluates to +3; the group’s sign must be saved with the frame.
Pattern takeaway
Nested structure plus a context that must survive the nesting (here: the running total and the sign applied to the group) is the signature of a stack of frames: push the context at every opener, reset, and on the closer pop and combine. Whether you keep that stack explicitly (Approach 2) or in the call stack (recursive descent), the frame contents are the design decision — figure out exactly what state a ( endangers, and push precisely that.