Problem statement

https://leetcode.com/problems/basic-calculator/

Solution

Quite painful problem, for me the easiest way is the following: go from left to right and when we see open bracket (, we do recursion, when we see closed bracket (, we return the evaluated value and the current place, where we finished. If we see + or -, we put elements in stack, if we see * and /, we update last element in stack. See problem 0227 Basic Calculator II for more explanations.

Complexity

Time and memory complexity is O(n).

Code

class Solution:
    def calculate(self, s):    
        def calc(it):
            def update(op, v):
                if op == "+": stack.append(v)
                if op == "-": stack.append(-v)
        
            num, stack, sign = 0, [], "+"
            
            while it < len(s):
                if s[it].isdigit():
                    num = num * 10 + int(s[it])
                elif s[it] in "+-":
                    update(sign, num)
                    num, sign = 0, s[it]
                elif s[it] == "(":
                    num, j = calc(it + 1)
                    it = j - 1
                elif s[it] == ")":
                    update(sign, num)
                    return sum(stack), it + 1
                it += 1
            update(sign, num)
            return sum(stack)

        return calc(0)

Remark

If we do not have * and /, then algorithm can be simplified, actually what we need is sigh of number in the end and we need to change it depending on our brackets.