Basic Calculator

The problem description can be found in LeetCode.

Approach

Solution

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

        i = 0
        while i < len(s):
            char = s[i]

            if char.isdigit():
                j = i
                while i < len(s) and s[i].isdigit():
                    i += 1

                num = int(s[j:i])
                continue

            if char == "+" or char == "-":
                res += sign * num
                sign = 1 if char == "+" else -1
                num = 0
            elif char == "(":
                stack.append(res)
                stack.append(sign)

                sign = 1
                res = 0
            elif char == ")":
                assert len(stack) > 1

                res += sign * num
                res *= stack.pop()
                res += stack.pop()

                num = 0

            i += 1

        return res + (sign * num)

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the nums list.