LeetCode 224: Basic Calculator

Problem Restatement

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

The expression may contain:

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

Example function shape:

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

Examples

Example 1:

s = "1 + 1"

Result:

2

Example 2:

s = " 2-1 + 2 "

Evaluation:

2 - 1 + 2 = 3

Result:

3

Example 3:

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

Inside parentheses:

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

Result:

23

First Thought

Without parentheses, the problem is simple.

For an expression like:

"2-1+2"

we can scan from left to right with:

When we finish reading a number, we add:

sign * number

to the result.

The hard part is parentheses.

Key Insight

Parentheses create a nested expression.

When we see:

"5 - (2 + 3)"

we need to remember two things before entering the parentheses:

For:

5 - (2 + 3)

before (, we have:

previous result = 5
previous sign = -1

Inside parentheses:

2 + 3 = 5

When ) appears, combine:

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:

current result
current sign

Then reset:

result = 0
sign = 1

because we are starting a new sub-expression.

When we leave a parenthesis, pop:

previous sign
previous result

Then combine:

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:

s = "5-(2+3)"

Start:

result = 0
sign = 1
stack = []

Read 5:

result = 5

Read -:

sign = -1

Read (.

Push current state:

stack = [5, -1]

Reset for sub-expression:

result = 0
sign = 1

Read 2:

result = 2

Read +:

sign = 1

Read 3:

result = 5

Read ).

Pop:

previous_sign = -1
previous_result = 5

Combine:

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

Final answer:

0

Handling Unary Minus

The input may contain unary -, such as:

"-1"

or:

"-(2+3)"

The same algorithm handles this naturally.

For "-1":

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

Result:

-1

For "-(2+3)":

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

Result:

-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

Where n = len(s).

Implementation

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:

result = 0
sign = 1
stack = []

Use an index loop because numbers may contain multiple digits:

while i < len(s):

When a digit starts, read the full number:

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

Then add it with the current sign:

result += sign * number

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

For + and -, update the sign:

sign = 1
sign = -1

When entering parentheses, save current state:

stack.append(result)
stack.append(sign)

Then reset for the inner expression:

result = 0
sign = 1

When closing parentheses, restore and combine:

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

result = previous_result + previous_sign * result

Finally return the evaluated result:

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.

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

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