# LeetCode 772: Basic Calculator III

## Problem Restatement

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

The expression may contain:

```text
non-negative integers
+
-
*
/
(
)
spaces
```

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

The expression follows normal arithmetic rules:

1. Parentheses are evaluated first.
2. Multiplication and division happen before addition and subtraction.
3. Operators with the same precedence are evaluated from left to right.
4. Integer division truncates toward zero.
5. We cannot use built-in expression evaluators like `eval`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A valid expression string `s` |
| Output | The integer value of the expression |
| Operators | `+`, `-`, `*`, `/` |
| Parentheses | Supported |
| Division | Truncates toward zero |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
2
```

Example 2:

```python
s = "6-4/2"
```

Output:

```python
4
```

Division happens before subtraction:

```text
4 / 2 = 2
6 - 2 = 4
```

Example 3:

```python
s = "2*(5+5*2)/3+(6/2+8)"
```

Output:

```python
21
```

Inside the first parentheses:

```text
5 + 5 * 2 = 15
```

So:

```text
2 * 15 / 3 = 10
```

Inside the second parentheses:

```text
6 / 2 + 8 = 11
```

Total:

```text
10 + 11 = 21
```

## First Thought: Use a Stack for Precedence

If there were no parentheses, this would be like Basic Calculator II.

We can scan the expression from left to right.

Addition and subtraction can be delayed by pushing signed numbers into a stack.

Multiplication and division must be applied immediately to the previous number.

For example:

```python
s = "6-4/2"
```

We push `6`.

Then we see `-4`, so we push `-4`.

Then `/2` should apply to the previous number, so `-4 / 2 = -2`.

The stack becomes:

```python
[6, -2]
```

The final sum is:

```text
6 + (-2) = 4
```

Parentheses add one extra requirement: when we see `(`, we recursively evaluate everything until the matching `)`.

## Key Insight

Use recursive parsing.

Define a helper function that evaluates the current expression until either:

1. the end of the string
2. a closing parenthesis `)`

Inside each recursive call, use the same stack idea:

| Operator | Action |
|---|---|
| `+` | Push `num` |
| `-` | Push `-num` |
| `*` | Pop previous value, multiply by `num`, push result |
| `/` | Pop previous value, divide by `num`, truncate toward zero, push result |

When the helper sees `(`, it recursively evaluates the inner expression and treats the returned value as the current number.

## Handling Division

Python integer division with `//` floors toward negative infinity.

But the problem requires truncation toward zero.

For example:

```text
-3 / 2 = -1
```

Python gives:

```python
-3 // 2 == -2
```

So we should use:

```python
int(a / b)
```

This truncates toward zero.

For LeetCode constraints, intermediate values fit in 32-bit signed integer range.

## Algorithm

1. Keep a shared index `i` into the string.
2. Define `parse()` to evaluate from `i` until `)` or end.
3. Inside `parse()`:
   1. Create an empty stack.
   2. Set `num = 0`.
   3. Set `op = "+"`.
4. Scan characters:
   1. Skip spaces.
   2. If the character is a digit, build the full number.
   3. If the character is `(`, recursively parse the subexpression.
   4. If the character is an operator, `)`, or the end:
      1. Apply the previous operator `op` to `num`.
      2. Set `op` to the current operator.
      3. Reset `num`.
   5. If the character is `)`, stop this recursive call.
5. Return `sum(stack)`.

## Correctness

The parser evaluates each parenthesized expression in its own recursive call. Therefore, every expression inside parentheses is fully evaluated before it is used by the outer expression.

Within one expression level, the stack enforces operator precedence. Addition and subtraction push signed values into the stack, so they are delayed until the end of the current expression. Multiplication and division immediately combine the current number with the previous stack value, so they are evaluated before surrounding additions and subtractions.

The scan processes operators from left to right. Since multiplication and division are applied immediately when encountered, operations with equal precedence are evaluated in the correct order.

Every number or parenthesized subexpression is consumed exactly once and combined with the operator before it. Therefore, the recursive parser computes the same value as the original arithmetic expression.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed once |
| Space | `O(n)` | The stack and recursion depth may grow linearly |

## Implementation

```python
class Solution:
    def calculate(self, s: str) -> int:
        i = 0

        def apply(stack: list[int], op: str, num: int) -> None:
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop() / num))

        def parse() -> int:
            nonlocal i

            stack = []
            num = 0
            op = "+"

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

                if ch == " ":
                    i += 1
                    continue

                if ch.isdigit():
                    num = 0

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

                    continue

                if ch == "(":
                    i += 1
                    num = parse()
                    continue

                apply(stack, op, num)
                num = 0

                if ch == ")":
                    i += 1
                    break

                op = ch
                i += 1

            return sum(stack)

        return parse()
```

## Code Explanation

The variable `i` is the current position in the string:

```python
i = 0
```

It is shared by recursive calls.

The helper `apply` applies the previous operator to the current number:

```python
def apply(stack: list[int], op: str, num: int) -> None:
```

For `+` and `-`, we push signed numbers.

For `*` and `/`, we combine with the previous stack value immediately.

```python
stack.append(stack.pop() * num)
stack.append(int(stack.pop() / num))
```

The parser begins with:

```python
stack = []
num = 0
op = "+"
```

The initial `+` means the first number should be pushed as positive.

When we see a digit, we build the full multi-digit number:

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

When we see an opening parenthesis:

```python
if ch == "(":
    i += 1
    num = parse()
    continue
```

the recursive call evaluates the whole inner expression and returns its value.

When we see an operator or closing parenthesis, we apply the previous operator:

```python
apply(stack, op, num)
```

If the character is `)`, this subexpression is complete:

```python
if ch == ")":
    i += 1
    break
```

At the end of a parse call:

```python
return sum(stack)
```

returns the value of the current expression level.

## Important Implementation Note

The implementation above needs one sentinel operator at the end to force the last pending number to be applied.

A simple way is to append `+` to the expression before parsing.

Here is the corrected full implementation:

```python
class Solution:
    def calculate(self, s: str) -> int:
        s += "+"
        i = 0

        def apply(stack: list[int], op: str, num: int) -> None:
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop() / num))

        def parse() -> int:
            nonlocal i

            stack = []
            num = 0
            op = "+"

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

                if ch == " ":
                    i += 1
                    continue

                if ch.isdigit():
                    num = 0

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

                    continue

                if ch == "(":
                    i += 1
                    num = parse()
                    continue

                apply(stack, op, num)
                num = 0

                if ch == ")":
                    i += 1
                    break

                op = ch
                i += 1

            return sum(stack)

        return parse()
```

## Testing

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

    assert s.calculate("1+1") == 2
    assert s.calculate("6-4/2") == 4
    assert s.calculate("2*(5+5*2)/3+(6/2+8)") == 21
    assert s.calculate("(2+6*3+5-(3*14/7+2)*5)+3") == -12
    assert s.calculate("10/3") == 3
    assert s.calculate("14-3/2") == 13
    assert s.calculate(" 3 + 5 / 2 ") == 5

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"1+1"` | Basic addition |
| `"6-4/2"` | Division before subtraction |
| Complex expression | Parentheses and precedence together |
| Nested expression | Confirms recursive parsing |
| `"10/3"` | Positive truncating division |
| `"14-3/2"` | Division before subtraction |
| Spaces | Confirms whitespace is ignored |