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

使用分治的思想实现，把大问题划分成为一个一个小问题实现。

刚开始理解的时候花了不少时间，但是拿笔在纸上画一下，其实思路立马就清晰了。

import org.omg.PortableInterceptor.INACTIVE;

import java.util.ArrayList;
import java.util.List;


public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String expression = "2*3-4*5";
        System.out.println(solution.diffWaysToCompute(expression));
    }

    
    public List diffWaysToCompute(String expression) {
        int n = expression.length();
        List ans = new ArrayList<>();
        for (int i = 0; i < n; i++){
            char c = expression.charAt(i);
            // 判断当前值是不是一个字符
            if (c == '+' || c == '-' || c == '*' ){
                // 获取左边的所有数的结果集
                List left = diffWaysToCompute(expression.substring(0 , i));
                List right = diffWaysToCompute(expression.substring(i + 1));
                for (Integer x : left) {
                    for (Integer  y : right){
                        switch (c){
                            case '+':
                                ans.add(x + y);
                                break;
                            case '-':
                                ans.add(x - y);
                                break;
                            case '*':
                                ans.add(x * y);
                                break;
                        }
                    }
                }
            }
        }
        if (ans.size() == 0){
            ans.add(Integer.parseInt(expression));
        }
        return ans;
    }
}