Python solution with comments.


  • 0
    C
    # Recursively, TLE
    # every time find the most inner parentheses and compute 
    # the value inside it, do this process recursively
    def calculate1(self, s):
        r = s.find(")") 
        if r == -1:
            return self.cal(s)
        l = s.rfind("(", 0, r)
        return self.calculate(s.replace(s[l:r+1], str(self.cal(s[l+1:r])), 1))
        
    def calculate(self, s):
        stack, i = [], 0
        while i < len(s):
            while i < len(s) and s[i] != ")":
                stack.append(s[i])
                i += 1
            tmp = ""
            while stack and stack[-1] != "(":
                tmp = stack.pop() + tmp
            t = self.cal(tmp)
            if stack:
                stack.pop() # pop out "("
            if t < 0 and stack:
                # tackle case like "2--1"
                if stack[-1] == "-":
                    stack[-1] = "+"
                # tackle case like "2+-1"
                else:
                    stack[-1] = "-"
                stack.append(str(-t))
            else:
                stack.append(str(t))
            i += 1
        return self.cal("".join(stack))
    
    # calculate the value of a string without parentheses,
    # like: "  +1 - 3  + 4  " = 2
    def cal(self, s):
        res, i = 0, 0
        while i < len(s):
            sign = 1
            if s[i] in ["-", "+"]:
                if s[i] == "-":
                    sign = -1
                i += 1
            while i < len(s) and s[i] == " ":
                i += 1
            tmp = 0
            while i < len(s) and s[i].isdigit():
                tmp = 10*tmp + int(s[i])
                i += 1
            res += sign*tmp 
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.