题目
给你一个由数字和运算符组成的字符串 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; } };
