241. Different Ways to Add Parentheses (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def diffWaysToCompute(self, expression):
        """
        :type expression: str
        :rtype: List[int]
        """
        def cal(a, op, b):
            if op == "+":
                return a + b
            if op == "-":
                return a - b
            if op == "*":
                return a * b
        def dfs(numbers, operators):
            res = []
            for i, op in enumerate(operators):
                if i == 0:
                    left = [numbers[0]]
                else:
                    left = dfs(numbers[ : i + 1], operators[ : i])
                if i == len(operators) - 1:
                    right = [numbers[-1]]
                else:
                    right = dfs(numbers[i + 1 : ], operators[i + 1 : ])
                for num1 in left:
                    for num2 in right:
                        res.append(cal(num1, op, num2))
            return res
        numbers, operators = [], []
        cur = ""
        for c in expression:
            if c.isdigit():
                cur += c
            else:
                numbers.append(int(cur))
                operators.append(c)
                cur = ""
        numbers.append(int(cur))
        if len(numbers) == 1:
            return numbers
        return dfs(numbers, operators)