241. 为运算表达式设计优先级（分治）

241. 为运算表达式设计优先级

• 题目
• 解题思路
• 代码

题目

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

解题思路

看到题就觉得有点复杂，可以考虑一下递归的方式，去寻找子问题和原问题解的关系。
可以通过运算符把整个式子分成两部分，两部分再利用递归解决。
以 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]。
另外两种情况也类似。
然后还需要递归出口。
如果给定的字符串只有数字，没有运算符，那结果就是给定的字符串转为数字。
比如上边的第一种情况，2 的解就是 [2]。

代码

给代码的最后临时加一行代码来见证result的历程

以input="2-1-1"为例： 可以看出，最后一次求出的result才是我们想要的结果

---

class Solution {
        public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<>();//用来存放结果的数组
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            //通过运算符将字符串分成两部分
            if (c == '+' || c == '-' || c == '*') {
                /*substring()：
                beginIndex -- 起始索引（包括）, 索引从 0 开始。
                endIndex -- 结束索引（不包括）。*/

                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int l : left) {
                    for (int r : right) {//两层循环可以保证每次取出一个left都有right和它对应
                        switch (c) {
                            case '+':
                                result.add(l + r);
                                break;
                            case '-':
                                result.add(l - r);
                                break;
                            case '*':
                                result.add(l * r);
                                break;
                        }
                    }
                }
            }
        }

        /*
        ①分治到最小了，无法在分了，因为分到最小，input.substring(0, i)是只有一个数字了，然后再进入diffWaysToCompute()
        会发现if循环只会执行一次，而且因为input里面只含有一个值，并且是个数字，不是符号，所以不会对result数组产生影响，
        即在该次递归中result的size为0.
        ②应对纯数字的情况，比如第一次输入的就是一个"12"。
         */
        if (result.size() == 0) {
            result.add(Integer.valueOf(input));
        }
        Collections.sort(result);//让result从小到大排序
        return result;
        /*
        在每次分治的调用diffWaysToCompute()时，都会返回一个result，即为分到最小的那个值，但并不是最终的结果，
        最终的结果是在分治的“分”到最小了，不能再分了，然后再合并起来的结果。即最后一次调用diffWaysToCompute()的result才是我们要的result，
        而分治过程中的result并不是我们想要的。
         */
    }
}