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

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

思路：

LeetCode 95. 不同的二叉搜索树 II

代码：

class Solution {
public:
    vector<string> expr;//把数字和符号拆开
    vector<int> diffWaysToCompute(string s) {
        int n = s.size();
        for(int i = 0; i < n; i++){ 
            if(isdigit(s[i])){
                int j = i;
                int x = 0;
                while(j < n && isdigit(s[j])) x = x * 10 + (s[j] - '0'),j++;
                expr.push_back(to_string(x));
                i = j - 1;
            }
            else expr.push_back(s.substr(i, 1));
        }
        return dfs(0,expr.size() - 1);
    }
    vector<int> dfs(int l,int r){
        if(l == r) return {stoi(expr[l])};
        vector<int> res;
        //枚举符号
        for(int i = l + 1; i < r; i += 2){
            auto left = dfs(l,i - 1);
            auto right = dfs(i + 1,r);
            for(auto x : left){
                for(auto y : right){
                    int t = 0;
                    if(expr[i] == "+") t = x + y;
                    else if(expr[i] == "-") t = x - y;
                    else t = x * y;
                    res.push_back(t);
                }
            }
        }
        return res;
    }
};