力扣（LeetCode） - 241 为运算表达式设计优先级

使用分治法求解

一、题目

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

示例1:

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

示例2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(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

二、思路

输入是一个string类型的运算表达式，要求为表达式添加括号，输出所有的组合的结果。我们可以用分治的思想，将每个运算符的左右两边分为两个部分，分别计算他们的值（也就相当于给左右两边分别加括号），这样就可以得到所有组合的结果。

我们可以这样设计我们的程序：遍历输入的表达式，如果遇到运算符，将表达式分为两个部分，然后使用递归计算左右两部分的运算结果，最后计算总的结果。

比如，我们计算 2 - 1 - 1的所有可能的结果。

三、代码

class Solution {
    //分治算法
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> list = new ArrayList<>();
        if(input.length() == 0) 
            return list;
        boolean flag = false;  //标志位，表示input中是否有运算符
        for(int i = 0; i < input.length(); ++i) {   //遍历input
            if(Character.isDigit(input.charAt(i))) continue;   //如果是数字，继续遍历
            flag = true;  //运行到这里说明input.charAt(i)是一个运算符
            List<Integer> lList = diffWaysToCompute(input.substring(0,i));  //计算运算符左边的结果，其长度一定为1
            List<Integer> rList = diffWaysToCompute(input.substring(i+1,input.length()));   //计算运算符右边的结果，其长度一定为1
            for(int m : lList){        //计算总结果
                for(int n : rList){
                    char op = input.charAt(i);
                    int result = 0;
                    switch (op){
                        case '+': result = m + n;break;
                        case '-': result = m - n;break;
                        case '*': result = m * n;break;
                    }
                    list.add(result);
                }
            }
        }
        if(flag == false) list.add(Integer.parseInt(input));  //没有运算符，将数组放入list中

        return list;
    }
}