HardMathStringStackRecursion

Basic Calculator

1 approach, code in every language

You are given a string that represents a valid arithmetic expression built from non-negative integers, the operators plus and minus, parentheses, and spaces. A minus sign may act as a unary operator, and parentheses can be nested to any depth to group subexpressions.

Evaluate the expression and return its integer value. You must implement the evaluation yourself rather than relying on any built-in function that parses or executes expressions.

Spaces may appear anywhere and should be ignored, and the final result is guaranteed to fit in a 32-bit signed integer.

Example 1

Input: s = "1 + 1"

Output: 2

The two operands are added together after the spaces are ignored.

Example 2

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

Output: 23

The inner group 4+5+2 is 11, so the first parenthesis gives 1+11-3 = 9, the second gives 14, and 9+14 = 23.

Constraints

1 <= s.length <= 3 * 10^5
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
The parentheses in s are always balanced.
The answer is guaranteed to fit in a 32-bit integer.

Running Result with Sign Stack

Keep a running result and current sign, and use a stack to save context whenever a parenthesis group opens.

Loading animation…

Intuition

Because only addition and subtraction are involved, the value of an expression is a running sum where every number is added with either a positive or negative sign. We keep a running result, a current sign that starts positive, and a number being assembled digit by digit. Encountering a plus or minus flushes the pending number into the result and sets the sign for whatever comes next. An opening parenthesis begins a fresh subexpression, so we push the current result and the sign that applies to the whole group onto a stack and reset both. A closing parenthesis finishes the group by flushing its number, multiplying the group's total by the saved sign, and adding back the saved result from before the group started.

Algorithm walkthrough

1Initialize the running result to zero, the pending number to zero, and the current sign to positive one.
2For each digit character, extend the pending number by multiplying by ten and adding the digit.
3On a plus or minus, add sign times the pending number into the result, reset the number, and set the sign accordingly.
4On an opening parenthesis, push the current result and then the current sign onto the stack, then reset the result to zero and the sign to positive one.
5On a closing parenthesis, flush the pending number, multiply the result by the sign popped from the stack, and add the result popped next.
6After the loop, flush any final pending number with the current sign and return the total.

Implementation

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        result = 0
        num = 0
        sign = 1
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == '+':
                result += sign * num
                num = 0
                sign = 1
            elif ch == '-':
                result += sign * num
                num = 0
                sign = -1
            elif ch == '(':
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            elif ch == ')':
                result += sign * num
                num = 0
                result *= stack.pop()
                result += stack.pop()
        return result + sign * num

Time

O(n)

Space

O(n)

Every character is processed once. The stack depth is proportional to the nesting depth of the parentheses, which is at most O(n).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Bracketed Offset Total is our own problem on the technique behind Basic Calculator: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free