LeetCode 224 - Basic Calculator

LeetCode Problem 224

Difficulty: 🔴 Hard
Topics: Math, String, Stack, Recursion

Solution

Problem Understanding

The problem gives us a string representing a mathematical expression containing integers, addition, subtraction, parentheses, and spaces. Our task is to evaluate the expression and return the final integer result.

The expression is guaranteed to be valid. That guarantee is extremely important because it simplifies parsing. We do not need to worry about malformed parentheses, invalid operators, or unexpected characters. Every expression contains only:

• Digits
• '+'
• '-'
• '('
• ')'
• Spaces

The calculator only needs to support addition and subtraction, but parentheses introduce nested expressions, which makes the problem more interesting. A simple left to right evaluation is not enough because expressions inside parentheses must be evaluated first.

For example:

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

requires us to evaluate nested subexpressions before combining them into the final result.

Another important detail is unary minus. Expressions like:

"-1"
"-(2+3)"

are valid. That means - does not always mean subtraction between two operands. Sometimes it changes the sign of the following value or subexpression.

The constraint:

1 <= s.length <= 3 * 10^5

is large. Any inefficient parsing strategy can easily time out. Repeated substring extraction or recursive re-parsing of large portions of the string would be too expensive. We need a solution that processes the string in linear time.

Some important edge cases include:

• Leading negative numbers such as "-5"
• Nested parentheses such as "((1+2)-3)"
• Unary minus before parentheses such as "-(3+(2-1))"
• Expressions with many spaces
• Multi-digit numbers such as "12345"
• Deeply nested expressions

The problem guarantees that all intermediate and final results fit inside a signed 32-bit integer, so overflow handling is not required.

Approaches

Brute Force Approach

A brute force strategy would attempt to repeatedly evaluate the innermost parenthesized expression. The algorithm could scan the string, locate matching parentheses, compute the value inside, replace that substring with the computed result, and continue until no parentheses remain.

For example:

"(1+(4+5))"

could become:

"(1+9)"

then:

"10"

This approach is logically correct because parentheses define independent subexpressions that can be reduced step by step.

However, repeatedly rebuilding strings is expensive. Every replacement operation may require copying most of the string. If the input length is large and deeply nested, the total complexity can become quadratic.

With a maximum length of 3 * 10^5, an O(n^2) solution is too slow.

Optimal Approach

The key observation is that addition and subtraction can be evaluated incrementally while scanning the string once from left to right.

We can maintain:

• A running result
• The current number being built
• The current sign
• A stack to remember state when entering parentheses

Whenever we encounter a (, we save the current result and sign because the parenthesized expression should be evaluated independently, then merged back into the outer expression.

Whenever we encounter a ), we finish evaluating the current subexpression and combine it with the previously saved context.

This allows us to process the expression in one pass with linear complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly rebuilds strings after evaluating parentheses
Optimal	O(n)	O(n)	Single pass using a stack for nested expressions

Algorithm Walkthrough

1. Initialize four variables:

• result stores the current accumulated value
• number stores the current number being parsed
• sign stores whether the current number should be added or subtracted
• stack stores previous computation states when entering parentheses

2. Iterate through the string character by character.
3. If the current character is a digit, build the number incrementally.

For example:

"123"

is processed as:

1 -> 12 -> 123

using:

number = number * 10 + int(char)

4. If the character is + or -, finalize the previous number by applying the current sign:

result += sign * number

Then update the sign for the next number:

• + means sign = 1
• - means sign = -1

Finally reset number to 0. 5. If the character is (, we are starting a new subexpression.

Before entering it:

• Push the current result onto the stack
• Push the current sign onto the stack

Then reset:

result = 0
sign = 1

This creates a fresh evaluation context for the inner expression. 6. If the character is ), first finish the current number:

result += sign * number

Then retrieve the previous sign and result from the stack:

prev_sign = stack.pop()
prev_result = stack.pop()

Combine them:

result = prev_result + prev_sign * result

Reset number to 0. 7. Ignore spaces because they do not affect evaluation. 8. After the loop finishes, one final number may still remain unapplied. Add it:

result += sign * number

9. Return the final result.

Why it works

The algorithm maintains the invariant that result always contains the evaluated value of the current expression scope, excluding the unfinished number.

Whenever parentheses begin, the previous computation state is preserved on the stack. When the parentheses close, the inner expression is fully evaluated and merged correctly into the outer expression using the saved sign and result.

Because every character is processed exactly once and nested contexts are managed with the stack, the algorithm correctly evaluates arbitrarily nested valid expressions.

Python Solution

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

        for char in s:
            if char.isdigit():
                number = number * 10 + int(char)

            elif char == '+':
                result += sign * number
                number = 0
                sign = 1

            elif char == '-':
                result += sign * number
                number = 0
                sign = -1

            elif char == '(':
                stack.append(result)
                stack.append(sign)

                result = 0
                sign = 1

            elif char == ')':
                result += sign * number
                number = 0

                prev_sign = stack.pop()
                prev_result = stack.pop()

                result = prev_result + prev_sign * result

        result += sign * number

        return result

The implementation follows the algorithm directly.

number accumulates multi-digit integers while scanning consecutive digit characters. This avoids expensive substring operations.

Whenever a + or - is encountered, the previously parsed number is committed into result using the current sign. The sign is then updated for the next number.

The stack stores two pieces of information whenever a new parenthesized expression begins:

• The result accumulated before the parenthesis
• The sign that should be applied to the parenthesized expression

When a closing parenthesis is reached, the current subexpression is completed and merged back into the outer expression using the saved context.

The final addition after the loop handles cases where the expression ends with a number rather than an operator or parenthesis.

Go Solution

func calculate(s string) int {
	result := 0
	number := 0
	sign := 1
	stack := []int{}

	for _, char := range s {
		if char >= '0' && char <= '9' {
			number = number*10 + int(char-'0')

		} else if char == '+' {
			result += sign * number
			number = 0
			sign = 1

		} else if char == '-' {
			result += sign * number
			number = 0
			sign = -1

		} else if char == '(' {
			stack = append(stack, result)
			stack = append(stack, sign)

			result = 0
			sign = 1

		} else if char == ')' {
			result += sign * number
			number = 0

			prevSign := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			prevResult := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			result = prevResult + prevSign*result
		}
	}

	result += sign * number

	return result
}

The Go implementation is nearly identical to the Python version. The main difference is explicit slice manipulation for the stack.

Go does not have Python's dynamic list pop operation, so we manually access the last element and shrink the slice.

Digit conversion is also slightly different:

int(char - '0')

converts a rune digit into its integer value.

The problem guarantees that all values fit inside a 32-bit signed integer, and Go's int type safely handles this range on LeetCode.

Worked Examples

Example 1

Input:

"1 + 1"

Character	number	sign	result	stack
1	1	1	0	[]
+	0	1	1	[]
1	1	1	1	[]

After loop:

result += 1 * 1 = 2

Final answer:

2

Example 2

Input:

" 2-1 + 2 "

Character	number	sign	result	stack
2	2	1	0	[]
-	0	-1	2	[]
1	1	-1	2	[]
+	0	1	1	[]
2	2	1	1	[]

After loop:

result += 1 * 2 = 3

Final answer:

3

Example 3

Input:

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

Character	number	sign	result	stack
(	0	1	0	[0,1]
1	1	1	0	[0,1]
+	0	1	1	[0,1]
(	0	1	0	[0,1,1,1]
4	4	1	0	[0,1,1,1]
+	0	1	4	[0,1,1,1]
5	5	1	4	[0,1,1,1]
+	0	1	9	[0,1,1,1]
2	2	1	9	[0,1,1,1]
)	0	1	12	[0,1]
-	0	-1	13	[0,1]
3	3	-1	13	[0,1]
)	0	-1	10	[]
+	0	1	10	[]
(	0	1	0	[10,1]
6	6	1	0	[10,1]
+	0	1	6	[10,1]
8	8	1	6	[10,1]
)	0	1	24	[]

Final answer:

23

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(n)	Stack may store nested parenthesis states

The algorithm performs a single linear scan through the input string. Every character contributes to constant-time operations such as updating numbers, modifying signs, or pushing and popping stack entries.

The stack size depends on the maximum nesting depth of parentheses. In the worst case, deeply nested expressions require O(n) stack space.

Test Cases

solution = Solution()

assert solution.calculate("1 + 1") == 2  # basic addition
assert solution.calculate(" 2-1 + 2 ") == 3  # spaces and subtraction
assert solution.calculate("(1+(4+5+2)-3)+(6+8)") == 23  # nested parentheses

assert solution.calculate("-1") == -1  # unary minus
assert solution.calculate("-(2+3)") == -5  # unary minus before parentheses
assert solution.calculate("10") == 10  # single number
assert solution.calculate("2147483647") == 2147483647  # large integer

assert solution.calculate("1-(2+3)") == -4  # subtraction with parentheses
assert solution.calculate("((1+2)-3)") == 0  # multiple nested parentheses
assert solution.calculate("1-(     -2)") == 3  # spaces with unary minus
assert solution.calculate("123+(456-78)") == 501  # multi-digit arithmetic

assert solution.calculate("(7)-(0)+(4)") == 11  # separated parenthesized terms
assert solution.calculate("0") == 0  # zero value
assert solution.calculate("((((5))))") == 5  # deeply nested single number

Test	Why
"1 + 1"	Verifies basic addition
" 2-1 + 2 "	Verifies spaces are ignored
"(1+(4+5+2)-3)+(6+8)"	Verifies nested parentheses
"-1"	Verifies unary minus
"-(2+3)"	Verifies unary minus before parentheses
"10"	Verifies single-number expressions
"2147483647"	Verifies large integer handling
"1-(2+3)"	Verifies subtraction of grouped expressions
"((1+2)-3)"	Verifies nested evaluation
"1-( -2)"	Verifies spaces and nested unary minus
"123+(456-78)"	Verifies multi-digit parsing
"(7)-(0)+(4)"	Verifies multiple grouped terms
"0"	Verifies zero handling
"((((5))))"	Verifies deeply nested parentheses

Edge Cases

Unary Minus at the Beginning

Expressions such as:

"-1"

can easily break parsers that assume every - is a binary subtraction operator. In this implementation, the sign variable handles unary minus naturally. When - appears before a number, the sign becomes -1, and the next parsed number is applied negatively.

Unary Minus Before Parentheses

Expressions like:

"-(2+3)"

are another common source of bugs. A naive implementation might fail to apply the negative sign to the entire subexpression.

This solution handles the case correctly by pushing the current sign onto the stack before entering the parenthesis. When the subexpression finishes, the stored sign is multiplied with the evaluated result.

Multi-Digit Numbers

A parser that processes digits independently would incorrectly evaluate:

"123"

as separate values 1, 2, and 3.

The implementation builds numbers incrementally using:

number = number * 10 + int(char)

which correctly forms arbitrarily large multi-digit integers.

Deeply Nested Parentheses

Expressions with many nested parentheses can cause recursive solutions to overflow the call stack.

This implementation uses an explicit stack data structure rather than recursive function calls, so it safely handles deeply nested expressions within the problem constraints.