Different Ways to Add Parentheses

Intuition

Solution

class Solution:
    def _operations_and_nums(self, input):
        operations, nums = [], []
        s = ''
        for c in input + '\0':
            if c in string.digits:
                s += c
            else:
                nums.append(int(s))
                s = ''
            if c in '+-*/':
                operations.append(c)
        return operations, nums

    def _operate(self, oper, i, j):
        if oper == '+':
            return i + j
        elif oper == '-':
            return i - j
        elif oper == '*':
            return i * j
        else:
            raise Exception

    def _helper(self, operations, nums):
        if len(nums) <= 1:
            return [sum(nums)]
        first_two = self._operate(operations[0], nums[0], nums[1])
        if len(nums) == 2:
            return [first_two]

        result = []
        for index in range(len(operations)):
            oper = operations[index]
            lefts = self._helper(operations[:index], nums[:index+1])
            rights = self._helper(operations[index+1:], nums[index+1:])
            for i in lefts:
                for j in rights:
                    result.append(self._operate(oper, i, j))

        return result

    def diffWaysToCompute(self, input: str) -> List[int]:
        operations, nums = self._operations_and_nums(input)

        return self._helper(operations, nums)