给你一个由数字和运算符组成的字符串 $expression$ ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：

((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2：

输入：expression = "23-45"
输出：[-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 <= expression.length <= 20$
$expression$ 由数字和算符 '+'、'-' 和 '*' 组成。输入表达式中的所有整数值在范围 [0, 99] 

题解:

分治法

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        int n = expression.size();
        for(int i = 0; i < n; i++) {
            char cur = expression[i];
            if(cur == '+' || cur == '-' || cur == '*') {  
                auto left = diffWaysToCompute(expression.substr(0, i));
                auto right = diffWaysToCompute(expression.substr(i+1));
                for(auto l : left) {
                    for(auto r : right) {
                        if(cur == '+') {
                            res.push_back(l + r);
                        }
                        else if(cur == '-') {
                            res.push_back(l - r);
                        }
                        else if(cur == '*') {
                            res.push_back(l * r);
                        }
                    }
                }
            }
        }
        if(res.empty()) {  // 纯数字， expression 中没有运算符
            res.push_back(stoi(expression));
        }
        return res;
    }
};