分治法

分治法

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

方法1：分治、递归

对于一个形如 x op y（op 为运算符，x 和 y 为数） 的算式而言，它的结果组合取决于 x 和 y 的结果组合数，而 x 和 y 又可以写成形如 x op y 的算式。

因此，该问题的子问题就是 x op y 中的 x 和 y：以运算符分隔的左右两侧算式解。

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        int n = expression.length();
        vector<int> ways;
        for (int i = 0; i < n; ++i) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                //1、分解：遇到运算符，计算左右两侧的结果集
                //2、解决：diffWaysTocompute递归函数求出子问题的解
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
                //3、合并：根据运算符合并子问题的解
                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                        case '-':ways.push_back(l - r); break;
                        case '+':ways.push_back(l + r); break;
                        case '*':ways.push_back(l * r); break;
                        }
                    }
                }
            }

        }
        if (ways.empty()) {
            ways.push_back(stoi(expression));
        }
        return ways;
    }
};