分治---给表达式加括号

给表达式加括号

241. Different Ways to Add Parentheses (Medium)

Input: "2-1-1".

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

Output : [0, 2]

题目描述：

  给出一个只有加，减，乘运算的表达式，要求在这个表达式中添加合理的括号，返回所有填上括号后的计算结果。

思路分析：

  考虑到每一个操作符（+，-，*），每一个操作符实际上是将表达式拆成了左右两部分。以2-1-1为例，第一个“-”，将表达式分成了两部分，分别是2，和1-1，那么就可以假定添加括号的结果是（2）-（1-1），同样的对左右两边进行操作，就将问题规模进行了缩小。直到不能拆分，直接返回。可以发现，到最后面，整个表达式都被拆分成一个一个数，然后逐层向上返回，将左右两边返回的结果进行不同的运算，继续向上返回。

代码：

public List<Integer>diffWaysToCompute(String input){
    List<Integer>ways=new ArrayList<>();
    for(int i=0;i<input.length();i++){
        char c=input.charAt(i);
        if(c=='+'||c=='-'||c=='*'){
        List<Integer>left=diffWaysToCompute(input.substring(0,i));
                    List<Integer>right=diffWaysToCompute(input.substring(i+1));
            for(int l:left){
                for(int r:right){
                    switch(c){
                        case '+':
                            ways.add(l+r);
                            break;
                        case '-':
                            ways.add(l-r);
                            break;
                        case '*':
                            ways.add(l*r);
                            break;
                    }
                }
            }
        }
    }
    if(ways.size()==0)
        ways.add(Integer.valueOf(input));
    return ways;
}