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

题目

题目连接

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

解题

方法一：dfs（分治）

class Solution {
    
public:
    vector<int> diffWaysToCompute(string expression) {
    
        return dfs(0,expression.size()-1,expression);
    }
    vector<int> dfs(int l,int r,string& s){
    
        vector<int> res;
        for(int i=l;i<=r;i++){
    
            if(s[i]>='0'&&s[i]<='9') continue;
            vector<int> l1=dfs(l,i-1,s);//分治：获得运算符左侧结果
            vector<int> l2=dfs(i+1,r,s);//分治：获得运算符右侧结果
            for(int a:l1){
    
                for(int b:l2){
    
                    int cur=0;
                    if(s[i]=='+') cur=a+b;
                    else if(s[i]=='-') cur=a-b;
                    else cur=a*b;
                    res.push_back(cur);
                }
            }
        }
        if(res.empty()){
    
            int num=0;
            for(int i=l;i<=r;i++){
    
                num=num*10+s[i]-'0';
            }
            res.push_back(num);
        }
        return res;
    }
};