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;

    }

};