Intuition

Compute values on the fly, use stack for brackets.

Approach

Parse each number, use num = 10xnum + current. Keep track of the last sign (starts as positive). When an opening bracket is found, stack the item and the sign. When a closing bracket is found, pop sign and item and do the math.

Complexity

  • Time complexity: O(N)

  • Space complexity: O(N)

Code

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        res = 0
        num = 0
        sign = 1
        for c in s:
            if c.isdigit():
                num  = (num * 10 ) + int(c)
            elif c == "+":
                res += sign * num
                sign = 1
                num = 0
            elif c == "-":
                res += sign * num
                sign = -1
                num = 0
            elif c == "(":
                stack.append(res)
                stack.append(sign)
                sign = 1
                res = 0
            elif c == ")":
                res += sign * num
                res *= stack.pop() # sign
                res += stack.pop() # num
                num = 0
        return res + sign * num