Different Ways to Add Parentheses

leetcode上的题目
给出一段只包含'+'、'-'、'*'和数字的式子，将式子分组（用小括号（）），求所有可能的结果。

例子：
Input: "2 * 3-4 * 5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

我的想法是：利用分治的思想，将问题分解成若干类似的小问题，求解小问题，再将答案组合起来。

假设改操作为函数(f(x))，递推公式的话 拿例子2*3-4*5来说，
$f(2 * 3-4 * 5)= lbrace f(2) * f(3-4 * 5),f(2 * 3)-f(4 * 5),f(2 * 3-4) * f(5) brace ( )f(3-4 * 5)= lbrace f(3) - f(4 * 5),f(3-4) * f(5) brace ( )f(3)= lbrace 3 brace (，)f(4 * 5)= lbrace 20 brace $

有了递推公式，我写的代码：

    def diffWaysToCompute(self, input):
        ints,operators=self.str2int(input)
        res=self.diffWaysToCompute_2(ints,operators)
        res.sort()
        return res

    def diffWaysToCompute_2(self,ints,operators):
        res=[]
        if ints is None:
            return res
        if len(ints)==1:
            return ints
        n=len(operators)
        for i in xrange(n):
            res_l=self.diffWaysToCompute_2(ints[:i+1],operators[:i])
            res_r=self.diffWaysToCompute_2(ints[i+1:],operators[i+1:])
            for j in xrange(len(res_l)):
                for k in xrange(len(res_r)):
                    res.append(self.compute(res_l[j],res_r[k],operators[i]))
        return res

    def compute(self,a,b,s):
    	if s=='+':
    		return a+b
    	if s=='-':
    		return a-b
    	if s=='*':
    		return a*b

    def str2int(self ,str):
        ints=[]
        operators=[]
        d=0
        for i in str:
            if i !='*' and i !='+' and i !='-':
                d=10*d+int(i)
            else:
                ints.append(d)
                d=0
                operators.append(i)
        ints.append(d)
        return ints,operators