题目描述

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

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1

这道题目采用分治法来解决，题目要求实现函数diffWaysToCompute，输入算数表达式input，输出不同的括号组合产生的计算结果列表ans。首先，我们扫描input寻找操作符即+、-和*。如果在input中找不到任何一个运算符，那么它就是操作数，我们将它转化为数字类型，加入到ans中返回即可。否则，input是包含运算符的表达式，情况变得复杂。

如果遇到了操作符，则将input分割成左右两部分，左右两部分可能还是一个计算表达式，我们继续将它送给函数diffWaysToCompute递归的处理，得到左右两部分返回值leftOpnds与rightOpnds。我们将leftOpnds和rightOpnds按照操作符optr做笛卡尔积，将运算结果加入到ans中就完成了对运算符的处理，我们编写了函数calculate(char optr, List leftOpnds, List rightOpnds)来实现这个功能。

private List<Integer> calculate(char optr, List<Integer> leftOpnds, List<Integer> rightOpnds) {
    List<Integer> result = new ArrayList<>();
    for (Integer leftOpnd : leftOpnds) {
        for (Integer rightOpnd : rightOpnds) {
            switch (optr) {
                case '+':
                    result.add(leftOpnd + rightOpnd);
                    break;
                case '-':
                    result.add(leftOpnd - rightOpnd);
                    break;
                case '*':
                    result.add(leftOpnd * rightOpnd);
                    break;
            }
        }
    }
    return result;
}

举一个例子，对于表达式input = “2*3-4*5″，先处理第一个运算符*，将input分割成左右两个表达式”2″和”3-4*5″。假设我们已经知道了”3-4*5″能产生结果列表[-5, -17]（后面会说怎么算出来的）。那么将2与[-5, -17]做乘法就能得到[-10, -34]，这只是计算结果的一部分，我么还要继续处理input下一个运算符’-‘，直到整个input处理完毕。至于刚刚提到的”3-4*5″怎么算出来的[-10, -34]，这又是一个子问题，按照相同的方法就能计算出来。

这是一种Top-down的解决问题方式，给定input就会递归的向下计算，这存在重复计算的问题。为了避免重复计算，需要使用Map<String, List<Integer>> cache来存储已经计算过的结果。全部代码如下：

class Solution {
    private Map<String, List<Integer>> cache = new HashMap<>();

    private List<Integer> calculate(char optr, List<Integer> leftOpnds, List<Integer> rightOpnds) {
        List<Integer> result = new ArrayList<>();
        for (Integer leftOpnd : leftOpnds) {
            for (Integer rightOpnd : rightOpnds) {
                switch (optr) {
                    case '+':
                        result.add(leftOpnd + rightOpnd);
                        break;
                    case '-':
                        result.add(leftOpnd - rightOpnd);
                        break;
                    case '*':
                        result.add(leftOpnd * rightOpnd);
                        break;
                }
            }
        }
        return result;
    }

    public List<Integer> diffWaysToCompute(String input) {
        if (input.length() == 0)
            return Collections.emptyList();
        List<Integer> ans = cache.get(input);
        if (ans != null)
            return ans;
        ans = new ArrayList<>();

        boolean hasOptr = false;
        for (int i = 0; i < input.length(); i++) {
            char currCh = input.charAt(i);
            if (currCh == '+' || currCh == '-' || currCh == '*') {
                List<Integer> leftOpnds = diffWaysToCompute(input.substring(0, i));
                List<Integer> rightOpnds = diffWaysToCompute(input.substring(i + 1));
                ans.addAll(calculate(currCh, leftOpnds, rightOpnds));
                hasOptr = true;
            }
        }

        if (!hasOptr) {
            ans.add(Integer.valueOf(input));
        }
        cache.put(input, ans);
        return ans;
    }
}