Different Ways to Add Parentheses

Problem: Different Ways to Add Parentheses

Actually we are not going to consider this problem as adding parentheses but just calculating operators in different order. Thus we can use divide and conquer to solve this problem.

Code in Python:

class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        def calc(l, r):
            ans = []
            for i in xrange(l, r):
                if input[i] not in oper:
                    continue
                ans += [oper[input[i]](lv, rv) for lv in calc(l, i)
                                              for rv in calc(i+1, r)]
            return ans if len(ans) > 0 else [int(input[l:r])]
        oper = {
            '-': lambda x, y: x-y,
            '+': lambda x, y: x+y,
            '*': lambda x, y: x*y,
            }
        return calc(0, len(input))

We just pick one of all operators each time and calculate it by splitting the expression into two parts and get their value. Thus by doing this in recurrence, we can iterate through all the possible answers.