Python recursive with comments


  • 0
    Y

    Firstly preprocess input string to create a list of integers, brackets and operators.
    Then iterate over the list. If we see an operator, store it. If we see an integer apply the operator and integer to the previous calculation. If we see an opening bracket then recurse until the closing bracket.

        def calculate(self, s):
            digits = {str(i) for i in range(10)}
            expression = ['(']      # wrap whole expression with brackets, easily identifies end
    
            for c in s:             # pre-process string into list of operators, brackets and ints
                if c == ' ':        # ignore blanks
                    continue
                if c not in digits: # operator or bracket
                    expression.append(c)
                elif isinstance(expression[-1], int):   # extending integer
                    expression[-1] = expression[-1]*10 + int(c)
                else:                                   # new integer
                    expression.append(int(c))
    
            expression.append(')')
            result, _ = self.evaluate(expression, 1)
            return result
    
    
        def evaluate(self, expression, i):      # evaluate from index i onwards to closing bracket
            calc, operator = 0, '+'
            while expression[i] != ')':
    
                atom = expression[i]
                if atom == '+' or atom == '-':  # store the operator
                    operator = atom
                else:                           # open bracket or integer
                    if isinstance(atom, int):
                        num = atom
                    else:                       # recurse on bracketed expression
                        num, i = self.evaluate(expression, i+1)
    
                    if operator == '+':         # apply operator to num
                        calc += num
                    else:
                        calc -= num
                i += 1
    
            return calc, i      # return calculation and index of closing bracket
    

Log in to reply
 

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