# LeetCode 224: Basic Calculator

## Problem Restatement

We are given a string `s` representing a valid arithmetic expression.

The expression may contain:

| Token | Meaning |
|---|---|
| Digits | Non-negative integers |
| `+` | Addition |
| `-` | Subtraction or unary negative |
| `(` | Start of a sub-expression |
| `)` | End of a sub-expression |
| Space | Ignored |

We need to evaluate the expression and return the integer result.

We cannot use built-in expression evaluators such as `eval`.

The official statement asks us to implement a calculator for a valid expression string. The constraints include `1 <= s.length <= 3 * 10^5`, valid characters are digits, `+`, `-`, `(`, `)`, and spaces, `+` is not unary, `-` may be unary, and every number and running result fits in a signed 32-bit integer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | String expression `s` |
| Output | Integer evaluation result |
| Operators | `+` and `-` |
| Parentheses | Supported, including nested parentheses |
| Spaces | Ignored |
| Forbidden | Built-in expression evaluation |

Example function shape:

```python
def calculate(s: str) -> int:
    ...
```

## Examples

Example 1:

```python
s = "1 + 1"
```

Result:

```python
2
```

Example 2:

```python
s = " 2-1 + 2 "
```

Evaluation:

```text
2 - 1 + 2 = 3
```

Result:

```python
3
```

Example 3:

```python
s = "(1+(4+5+2)-3)+(6+8)"
```

Inside parentheses:

```text
4 + 5 + 2 = 11
1 + 11 - 3 = 9
6 + 8 = 14
9 + 14 = 23
```

Result:

```python
23
```

## First Thought

Without parentheses, the problem is simple.

For an expression like:

```python
"2-1+2"
```

we can scan from left to right with:

| Variable | Meaning |
|---|---|
| `result` | Sum accumulated so far |
| `sign` | `1` for plus, `-1` for minus |
| `number` | Current multi-digit number being read |

When we finish reading a number, we add:

```python
sign * number
```

to the result.

The hard part is parentheses.

## Key Insight

Parentheses create a nested expression.

When we see:

```python
"5 - (2 + 3)"
```

we need to remember two things before entering the parentheses:

| Saved value | Meaning |
|---|---|
| Previous result | The value before the parentheses |
| Previous sign | Whether the parenthesized expression should be added or subtracted |

For:

```text
5 - (2 + 3)
```

before `(`, we have:

```text
previous result = 5
previous sign = -1
```

Inside parentheses:

```text
2 + 3 = 5
```

When `)` appears, combine:

```text
previous result + previous sign * inside result
= 5 + (-1 * 5)
= 0
```

This is exactly what a stack is for.

## Stack State

When we enter a parenthesis, push:

```text
current result
current sign
```

Then reset:

```text
result = 0
sign = 1
```

because we are starting a new sub-expression.

When we leave a parenthesis, pop:

```text
previous sign
previous result
```

Then combine:

```python
result = previous_result + previous_sign * result
```

## Algorithm

1. Initialize:
   - `result = 0`
   - `sign = 1`
   - `stack = []`
   - `i = 0`
2. Scan the string.
3. If the current character is a digit:
   - read the whole multi-digit number
   - add `sign * number` to `result`
4. If the character is `+`:
   - set `sign = 1`
5. If the character is `-`:
   - set `sign = -1`
6. If the character is `(`:
   - push `result`
   - push `sign`
   - reset `result = 0`, `sign = 1`
7. If the character is `)`:
   - pop sign
   - pop previous result
   - combine the current sub-expression with the outer expression
8. Ignore spaces.
9. Return `result`.

## Walkthrough

Use:

```python
s = "5-(2+3)"
```

Start:

```text
result = 0
sign = 1
stack = []
```

Read `5`:

```text
result = 5
```

Read `-`:

```text
sign = -1
```

Read `(`.

Push current state:

```text
stack = [5, -1]
```

Reset for sub-expression:

```text
result = 0
sign = 1
```

Read `2`:

```text
result = 2
```

Read `+`:

```text
sign = 1
```

Read `3`:

```text
result = 5
```

Read `)`.

Pop:

```text
previous_sign = -1
previous_result = 5
```

Combine:

```text
result = 5 + (-1 * 5) = 0
```

Final answer:

```python
0
```

## Handling Unary Minus

The input may contain unary `-`, such as:

```python
"-1"
```

or:

```python
"-(2+3)"
```

The same algorithm handles this naturally.

For `"-1"`:

- start with `result = 0`
- read `-`, so `sign = -1`
- read `1`, add `-1 * 1`

Result:

```python
-1
```

For `"-(2+3)"`:

- read `-`, so `sign = -1`
- read `(`, push `0` and `-1`
- evaluate inside as `5`
- combine `0 + (-1 * 5)`

Result:

```python
-5
```

## Correctness

The algorithm scans the expression from left to right.

For every number outside parentheses, it adds that number to the current expression using the current sign. This correctly handles addition and subtraction.

When the algorithm sees `(`, it saves the current expression result and the sign that applies to the upcoming parenthesized expression. It then starts a fresh calculation for the inside expression.

When it sees `)`, the inside expression has already been fully evaluated. The algorithm restores the outer state and combines it with the inside value using the saved sign.

Because the stack stores one state per open parenthesis, nested parentheses are handled in last-in, first-out order, exactly matching expression nesting.

Spaces are ignored and do not affect the value.

Therefore the algorithm evaluates the expression correctly.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each character is processed once |
| Space | `O(n)` | Stack may store nested parentheses |

Where `n = len(s)`.

## Implementation

```python
class Solution:
    def calculate(self, s: str) -> int:
        result = 0
        sign = 1
        stack = []
        i = 0

        while i < len(s):
            ch = s[i]

            if ch.isdigit():
                number = 0

                while i < len(s) and s[i].isdigit():
                    number = number * 10 + int(s[i])
                    i += 1

                result += sign * number
                continue

            if ch == "+":
                sign = 1
            elif ch == "-":
                sign = -1
            elif ch == "(":
                stack.append(result)
                stack.append(sign)

                result = 0
                sign = 1
            elif ch == ")":
                previous_sign = stack.pop()
                previous_result = stack.pop()

                result = previous_result + previous_sign * result

            i += 1

        return result
```

## Code Explanation

Initialize the running state:

```python
result = 0
sign = 1
stack = []
```

Use an index loop because numbers may contain multiple digits:

```python
while i < len(s):
```

When a digit starts, read the full number:

```python
number = number * 10 + int(s[i])
```

Then add it with the current sign:

```python
result += sign * number
```

The `continue` avoids incrementing `i` twice after reading a multi-digit number.

For `+` and `-`, update the sign:

```python
sign = 1
sign = -1
```

When entering parentheses, save current state:

```python
stack.append(result)
stack.append(sign)
```

Then reset for the inner expression:

```python
result = 0
sign = 1
```

When closing parentheses, restore and combine:

```python
previous_sign = stack.pop()
previous_result = stack.pop()

result = previous_result + previous_sign * result
```

Finally return the evaluated result:

```python
return result
```

## Alternative Sign-Stack Version

Another compact approach stores the current sign environment.

Instead of pushing both result and sign, we keep a global answer and a stack of signs.

```python
class Solution:
    def calculate(self, s: str) -> int:
        result = 0
        number = 0
        sign = 1
        stack = [1]

        for ch in s:
            if ch.isdigit():
                number = number * 10 + int(ch)
            elif ch in "+-":
                result += sign * number
                number = 0

                if ch == "+":
                    sign = stack[-1]
                else:
                    sign = -stack[-1]
            elif ch == "(":
                stack.append(sign)
            elif ch == ")":
                stack.pop()

        return result + sign * number
```

This version treats signs as inherited from parenthesized environments. The first stack version is easier to explain because it mirrors how expressions are grouped.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.calculate("1 + 1") == 2
    assert s.calculate(" 2-1 + 2 ") == 3
    assert s.calculate("(1+(4+5+2)-3)+(6+8)") == 23
    assert s.calculate("-1") == -1
    assert s.calculate("-(2+3)") == -5
    assert s.calculate("1-(2+3)") == -4
    assert s.calculate("10 + (20 - (3 + 4))") == 23

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"1 + 1"` | Basic addition |
| `" 2-1 + 2 "` | Spaces and mixed operators |
| Nested example | Parentheses and nesting |
| `"-1"` | Unary minus before number |
| `"-(2+3)"` | Unary minus before parentheses |
| `"1-(2+3)"` | Subtract parenthesized expression |
| Multi-digit nested case | Multi-digit parsing |