1. 具体题目

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:　　输入: "2-1-1"　　输出: [0, 2]　　解释:  ((2-1)-1) = 0；(2-(1-1)) = 2

2. 思路分析

分治 + 递归

3. 代码

 1 public List<Integer> diffWaysToCompute(String input) {
 2         List<Integer> ans = new ArrayList<>();
 3         for(int i = 0; i < input.length(); i++){
 4             char c = input.charAt(i);
 5             if(c == '+' || c == '-' || c == '*'){
 6                 List<Integer> left = diffWaysToCompute(input.substring(0, i));
 7                 List<Integer> right = diffWaysToCompute(input.substring(i + 1));
 8                 for(int l : left){
 9                     for(int r : right){
10                         if(c == '+') {
11                             ans.add(l + r);
12                         }else if (c == '-') {
13                             ans.add(l - r);
14                         }else{
15                             ans.add(l * r);
16                         }
17                     }
18                 }
19             }
20         }
21         if(ans.size() == 0){
22             ans.add(Integer.valueOf(input));
23         }
24         return ans;
25     }