Different Ways to Add Parentheses

要点：这题是另一种递归方式：分治，进一步说是catalan number方式的分治。比较有意思的是和Remove Invalid Parentheses这题的对比，remove里是从左到右递归。首先这题肯定不能这样递归，因为没法同步计算结果。另外，这题的特点是分治的两边是isolate的，意思就是两边加了括号，而每一个做中心的情况都延伸到边界，所以彼此也是isolate的。remove是基于每个存在的括号的，这个没法作为中心点。其他要点：

• 如何区分算符和数字？分割点只在算符，如果loop以后没有算符，那么substring是一个数，只有最深层会只返回这个数（类似于表达式可以用二叉树来表示，只有leaf是数）。所以是通过结果集来确定的
• 注意recursion function返回的是所有可能组合的结果，所以是list

class Solution(object):    def diffWaysToCompute(self, input):        """        :type input: str        :rtype: List[int]        """        def diffWays(input):            res = []            for i in xrange(len(input)):                if input[i] in '+-*/':                    left = diffWays(input[:i])                    right = diffWays(input[i+1:])                    for l in left:                        for r in right:                            if input[i]=='+':                                res.append(l+r)                            if input[i]=='-':                                res.append(l-r)                            if input[i]=='*':                                res.append(l*r)                            if input[i]=='/':                                res.append(l/r)            if not res:                res.append(int(input))            return res                return diffWays(input)