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. 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.
def calculate(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, giving O(n²) time and O(n) space. With n = 3 * 10^5 and deep nesting that is about 10^10 character operations, far too slow. The repeated string rebuilding is the bottleneck.
Approach 2 — One pass with a sign stack
With only + and -, subtraction is addition with a coefficient of −1, so there is no operator precedence to track, only a current sign. A ( interrupts that sign context. 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.
def calculate(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
Parentheses define a recursive grammar, so the call stack can serve as 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.
def calculate(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.
flowchart TD
A["parse outer: - ( ... )<br/>returns 0 + (-1)*2 = -2"]
B["parse middle: 5 - ( ... )<br/>returns 5 + (-1)*3 = 2"]
C["parse inner: 1 + 2<br/>returns 3"]
A -->|recurse on first '('| B
B -->|recurse on second '('| C
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 (about 1000), so the iterative Approach 2 is the safe submission. The recursive form is still useful to know 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) calls for 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. Identify exactly what state a ( interrupts, and push precisely that.