题目描述

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

样例

输入: "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

算法1

(分治)

知识背景：每个表达式都对应一棵表达式树，联想到leetcode95.不同的二叉搜索树

由于给定的是字符串，需要先对输入字符串进行处理，把数字和运算符分开
对于一个运算符，以这个运算符分割左右表达式，整体表达式的取值就是所有左边表达式的结果和所有右边表达式经过分割的运算符计算后的结果。
而对于左右两侧的表达式，也是运用同样的方式计算结果，所以用分治+递归的方式处理左右的表达式

时间复杂度为卡特兰数

Java 代码

class Solution {
    List<String> in = new ArrayList<>();
    public List<Integer> diffWaysToCompute(String input) {
        char[] c = input.toCharArray();
        for(int i = 0; i < input.length(); ){
            if(Character.isDigit(c[i])){
                int num = 0;
                while(i < input.length() && Character.isDigit(c[i])){
                    num = num * 10 + (c[i]-'0');
                    i++;
                }
                in.add(String.valueOf(num));
            }else {
                in.add(String.valueOf(c[i++]));
            }
        }
        return dfs(0, in.size()-1);
    }

    List<Integer> dfs(int l, int r){
        List<Integer> res = new ArrayList<>();
        if(l == r) {
            res.add(Integer.valueOf(in.get(l)));
            return res;
        }

        //枚举分割点
        for(int i = l + 1; i < r; i += 2){
            List<Integer> left = dfs(l, i-1), right = dfs(i+1, r);
            for(int x: left){
                for(int y: right){
                    int z = 0;
                    if(in.get(i).equals("+")){
                        z = x + y;
                    }else if(in.get(i).equals("-")){
                        z = x - y;
                    }else {
                        z = x * y;
                    }
                    res.add(z);
                }
            }
        }
        return res;
    }
}