LeetCode.241

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

题目大意

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

思路: 分治

我们对于每一个运算符可以考虑它左边可以运算出的值 和 右边可以运算出的值,他们两个再进行运算的值就是结果的可能值

class Solution {
public:
    int stoi(string s) {
        int cnt = 0;
        for(char c: s) {
            cnt = cnt * 10 + c - '0';
        }
        return cnt;
    }
    vector<int> diffWaysToCompute(string expression) {
        vector<int> count;
        int len = expression.size();
        cout << expression << endl;
        for(int i = 0; i < expression.size(); i ++ ) {            if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
                char c = expression[i];
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
                for(auto l : left)
                    for(auto r: right) {
                        if(c == '+')
                            count.push_back(l + r);
                        else if(c == '-')
                            count.push_back(l - r);
                        else
                            count.push_back(l * r);
                    }
            }
        }
        if(count.empty()) {
            count.push_back(stoi(expression));
        }
        return count;
    }
};

思路来自:HERODing