題目來源
可以用劃分的方法來做，就是每到一個符號唯袄，就把它割為兩塊弯屈，求出前面一塊和后面一塊的所有可能結(jié)果，然后再進(jìn)行運算恋拷，代碼如下：

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        int n = input.size();
        for (int i=0; i<n; i++) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*' ) {
                string part1 = input.substr(0, i);
                string part2 = input.substr(i+1);
                vector<int> res1 = diffWaysToCompute(part1);
                vector<int> res2 = diffWaysToCompute(part2);
                for (int num1 : res1)
                    for (int num2 : res2) {
                        if (input[i] == '+')
                            res.push_back(num1 + num2);
                        else if (input[i] == '-')
                            res.push_back(num1 - num2);
                        else
                            res.push_back(num1 * num2);
                    }
            }
        }
        if (res.empty())
            res.push_back(atoi(input.c_str()));
        return res;
    }
};

然后實際上計算過程中會有很多的重復(fù)計算资厉，可以用DP來解決這個問題。

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        unordered_map<string, vector<int>> maps;
        res = computeWithDP(input, maps);
        return res;
    }
    
    vector<int> computeWithDP(string input, unordered_map<string, vector<int>> &maps)
    {
        if (maps.count(input) != 0)
            return maps[input];
        vector<int> res;
        int n = input.size();
        for (int i=0; i<n; i++) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*' ) {
                string part1 = input.substr(0, i);
                string part2 = input.substr(i+1);
                vector<int> res1 = diffWaysToCompute(part1);
                vector<int> res2 = diffWaysToCompute(part2);
                for (int num1 : res1)
                    for (int num2 : res2) {
                        if (input[i] == '+')
                            res.push_back(num1 + num2);
                        else if (input[i] == '-')
                            res.push_back(num1 - num2);
                        else
                            res.push_back(num1 * num2);
                    }
            }
        }
        if (res.empty())
            res.push_back(atoi(input.c_str()));
        return res;
    }
};