We need to evaluate a mathematical expression that contains addition, subtraction, parentheses, and spaces. The expression only has + and - operators, no multiplication or division. The tricky part is handling nested parentheses correctly, because a minus sign before a parenthesized group flips the sign of everything inside it.

For example, in 1-(2+3), the minus before the parenthesis means we subtract both 2 and 3. So it evaluates to 1 - 2 - 3 = -4. Without parentheses, we could scan left to right. With them, we need a way to track the current sign context: when we enter a (, remember whether the surrounding expression was adding or subtracting, and when we hit ), restore the previous context.

Parentheses do not introduce precedence rules here, since only + and - appear. They only flip signs, so the core of the problem is tracking the cumulative sign as nested groups open and close.

Key Constraints:

Intuition

Process the expression character by character, keeping a running result. A ( interrupts the current computation: the value accumulated so far and the pending sign cannot be finished until the parenthesized group is evaluated, so they must be saved and restored afterward. A stack stores this saved state, and since groups close in the reverse order they open, last-in-first-out matches the order we need them back.

We maintain a running result and a sign variable (either +1 or -1) that records whether the next number gets added or subtracted. When we see a (, we push the current result and sign onto the stack, then reset result to 0 and sign to 1 to evaluate the group from scratch. When we see ), we pop the saved sign and saved result and combine: result = savedResult + savedSign * result.

Algorithm

Visualization and Code

The explicit stack saves and restores state by hand. Nested parentheses have the same shape as nested function calls, so the language's call stack can do that bookkeeping instead.

Intuition

A parenthesized group is a smaller expression of the same form, so the structure of the input is recursive. A helper function evaluates characters starting from a shared position index. When it meets a (, it calls itself to evaluate the group and adds the returned value with the pending sign. When it meets ) or the end of the string, it returns the value it has built. Each call keeps its own result and sign as local variables, which replaces the explicit stack from Approach 1 with call frames.

The shared position index is what keeps this O(n). The index only moves forward, and each recursive call resumes from wherever the inner call stopped, so every character is consumed once. Recursing on extracted substrings instead (find the matching ), cut out the middle, evaluate the copy) would re-scan and copy characters at every nesting level, which is quadratic on deeply nested input. With s.length up to 3 * 10^5, that distinction matters.

Algorithm

Visualization and Code

The recursion and the explicit stack both save one result and one sign per nesting level. The next approach drops the saved result entirely: it tracks only an effective sign per level, so every number adds directly into a single running total.

Intuition

Because parentheses only flip signs, the expression is equivalent to a flat sum: each number contributes number * (its own operator) * (product of the signs in front of every parenthesis enclosing it). If we can compute that cumulative product on the fly, every number adds straight into one running total. There is nothing to pause, reset, or recombine, and ) becomes a no-op apart from dropping one level of context.

Consider 1-(2+3). The minus before the parenthesis means the + inside effectively becomes a - in the global context, so both 2 and 3 get subtracted. In 1-(2-(3+4)), the outer - flips the inner + to -, but the inner - gets flipped back to +, so 3 and 4 are both added (a double negative).

Each time we enter a (, the sign preceding it multiplies into the current effective sign. We keep a stack of effective signs, where the top is the sign context for the current nesting level. Each number is multiplied by the top of the sign stack and by its immediate operator before being added to the result.

Algorithm

Visualization and Code