Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

1
2
((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

1
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]

思路

这道题如果先把所有的情况的算式用字符串的方式存储起来，再分别用中缀表达式转后缀表达式，会显得非常复杂。这也不是题意所要求的。

我们需要采用分治法来解决此问题。

分治法适用于什么样的情况呢？分治法所能解决的问题一般具有以下几个特征：

  1. 该问题的规模缩小到一定的程度就可以容易地解决

  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

  3. 利用该问题分解出的子问题的解可以合并为该问题的解；

  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

满足了以上条件，我们来遵循分治法的步骤分析这个问题。

首先，我们需要将原问题分解成为规模比较小的子问题；之后，我们需要递归地将子问题进行求解；最后，我们把子问题的解合并为原问题的解。这也就是分治法的三个步骤。

具体而言， "2*3-4*5"可以分解为以下三个子问题：2 / 345; 23 / 45; 234 / 5。我们在划分的时候，数字长度如果为n，我们就需要划分n-1次。每一次划分之间的结果相互独立，也满足了前文所述的分治法第四条特征。

解决子问题，就需要采取递归的方式。最后，将所求的答案输出到数组里即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        s = ["+","-","*"]
        digits = []
        symbols = []
        self.ans = []
        tmp = ''
        # 注意算式中数字和符号的划分
        for i in input:
            if i in s:
                symbols.append(i)
                digits.append(int(tmp))
                tmp = ''
            else:
                tmp += i
        digits.append(int(tmp))
                
        self.length = len(digits)
        return self.subproblem(digits, symbols)
        
    def subproblem(self, digits, symbols):
        n = len(digits)
        # 最后求得的结果用数组保存。
        # 因为当 n == 3 时，已经出现两个结果，返回值需放在数组当中
        result = []
        # 解决最简单的子问题 n == 1
        if (n == 1):
            return [digits[0]]
        # 在这个地方，有三个if语句的判断，可以将其放在一个helper函数里，会比较简洁。
        # n == 2 时的结果
        elif (n == 2):
            if (symbols[0] == '+'):
                result = [digits[0] + digits[1]]
            elif (symbols[0] == '-'):
                result = [digits[0] - digits[1]]
            elif (symbols[0] == '*'):
                result = [digits[0] * digits[1]]
            return result
        # n > 2
        else:
            for k in range(1, n):
                if (symbols[k-1] == "+"):
                    # 由于函数返回值是一个数组，我们将结果全部遍历
                    # 进行操作之后，得到新的一组结果
                    for i in self.subproblem(digits[:k], symbols[:k-1]):
                        for j in self.subproblem(digits[k:], symbols[k:]):
                            result.append(i + j)
                elif (symbols[k-1] == "-"):
                    for i in self.subproblem(digits[:k], symbols[:k-1]):
                        for j in self.subproblem(digits[k:], symbols[k:]):
                            result.append(i - j)
                elif (symbols[k-1] == "*"):
                    for i in self.subproblem(digits[:k], symbols[:k-1]):
                        for j in self.subproblem(digits[k:], symbols[k:]):
                            result.append(i * j)
                    
            return result