为运算表达式设定优先级

问题陈述

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

示例：

1
2
3
4
5
输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

思路分析

考虑使用分治法。

1、先对输入字符串进行判断，若为空，返回一个空列表结果。

2、若不空但全为数字，则直接获取该数字字符串所表示的整数值。

3、出现了运算符，则对字符串根据该运算符位置划分左列表和右列表。分别计算左列表结果和右列表结果，然后根据该运算符得到一个最后结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
以 2 * 3 - 4 * 5 为例。

2 和 3 - 4 * 5 两部分，中间是 * 号相连。

2 * 3 和 4 * 5 两部分，中间是 - 号相连。

2 * 3 - 4 和 5 两部分，中间是 * 号相连。

有了两部分的结果，然后再通过中间的符号两两计算加入到最终的结果中即可。

比如第一种情况，2 和 3 - 4 * 5 两部分，中间是 * 号相连。

2 的解就是 [2]，3 - 4 * 5 的解就是 [-5, -17]。

把两部分解通过 * 号计算，最终结果就是 [-10, -34]。

另外两种情况也类似。

代码实现

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
public class DiffWayToCompute {

    public List<Integer> diffToCompute(String input){
        //判空
        if(input.length()==0){
            return new ArrayList<>();
        }
        int index=0,num=0;
        List<Integer> result=new ArrayList<>();
        //全为数字的情况
        while(index<input.length()&&!isOperation(input.charAt(index))){
            num=num*10+input.charAt(index)-'0';//数字字符减0字符可以得到该字符对应数字。
            index++;
        }
        if(index==input.length()){
            result.add(num);
            return result;
        }
        //出现算术符
        for(int i=0;i<input.length();i++){
            if(isOperation(input.charAt(i))){
                List<Integer> result1=diffToCompute(input.substring(0,i));
                List<Integer> result2=diffToCompute(input.substring(i+1));
                for(int j=0;j<result1.size();j++){
                    for(int k=0;k<result2.size();k++){
                        char op=input.charAt(i);
                        result.add(calculate(result1.get(j),op,result2.get(k)));
                    }
                }
            }
        }
        return result;

    }
    private int calculate(int m, char op, int n){
        switch (op){
            case '+':
                return m+n;
            case '-':
                return m-n;
            case '*':
                return m*n;
        }
        return -1;
    }
    private boolean isOperation(char op){
        return ((op == '+')||(op=='-')||(op=='*'));
    }
}