给一个表达式字符串加括号，计算它的所有的可能的值

241. Different Ways to Add Parentheses

题意：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 *.

解法：利用分治发求解。和矩阵加括号类似。

代码如下

 1     public List<Integer> diffWaysToCompute(String input) {
 2         //int i = 0;
 3         List<Integer> res = helper(input);
 4 
 5         return res;
 6     }
 7 
 8     public List<Integer> helper(String input) {
 9         List<Integer> res = new ArrayList<>();
10         int i = 0;
11         int n = input.length();
12         while (i < n) {
13             //int j=i;
14             while (i < n && Character.isDigit(input.charAt(i))) i++;
15             if(i==n) break;
16             String s1 = input.substring(0, i);
17             String s2 = input.substring(i + 1);
18             char operator = input.charAt(i);
19             List<Integer> list1 = helper(s1);
20             List<Integer> list2 = helper(s2);
21             if (operator == '+') {
22                 for (int i1 : list1) {
23                     for (int i2 : list2) {
24                         res.add(i1 + i2);
25                     }
26                 }
27             } else if (operator == '-') {
28                 for (int i1 : list1) {
29                     for (int i2 : list2) {
30                         res.add(i1 - i2);
31                     }
32                 }
33             } else {
34                 for (int i1 : list1) {
35                     for (int i2 : list2) {
36                         res.add(i1 * i2);
37                     }
38                 }
39             }
40             i++;
41         }
42         if(res.isEmpty()) res.add(Integer.parseInt(input));
43         return res;
44     }