LeetCode 772: Basic Calculator III

Problem Restatement

We are given a valid arithmetic expression string s.

The expression may contain:

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

Example function shape:

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

Examples

Example 1:

s = "1+1"

Output:

2

Example 2:

s = "6-4/2"

Output:

4

Division happens before subtraction:

4 / 2 = 2
6 - 2 = 4

Example 3:

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

Output:

21

Inside the first parentheses:

5 + 5 * 2 = 15

So:

2 * 15 / 3 = 10

Inside the second parentheses:

6 / 2 + 8 = 11

Total:

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:

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:

[6, -2]

The final sum is:

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:

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:

-3 / 2 = -1

Python gives:

-3 // 2 == -2

So we should use:

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).

Implementation

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:

i = 0

It is shared by recursive calls.

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

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.

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

The parser begins with:

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:

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

When we see an opening parenthesis:

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:

apply(stack, op, num)

If the character is ), this subexpression is complete:

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

At the end of a parse call:

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:

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

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: