Python recursive with comments

  • 0

    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
                if c not in digits: # operator or bracket
                elif isinstance(expression[-1], int):   # extending integer
                    expression[-1] = expression[-1]*10 + int(c)
                else:                                   # new integer
            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
                        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.