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
 

提示：

1 <= expression.length <= 20
expression 由数字和算符 '+'、'-' 和 '*' 组成。
输入表达式中的所有整数值在范围 [0, 99] 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/different-ways-to-add-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

以前碰到这种运算符题总是头疼，觉得思考起来好麻烦啊，运算符该怎么处理等等，

碰巧今天每日一题就是这种题，老实讲，有些题我们为什么觉得困难，因为我们根本不愿意去思考，或者说去做，因此我们怕这种题，

但这次这是每日一题没办法，我又必须去做了。

确实，我看到题我能很明显的认识到，这是一道分治，递归的题目，但我也不知道该怎么处理每个分支

所幸去看了看题解，本来以为我又要硬着头皮去思考了，没想到却意外的好理解，

我们只用根据运算符分为左右两部分就好了

左部分的运算值存放到左边数组，右边的存放到右边数组，

显然递归结束的条件是一直找到不同分只下没有运算符的情况，那么这道题就比较好写了。当然这道题还有动规的方式，我也不太会哈

class Solution {
public:
    unordered_map<string,vector<int>>m;
    vector<int> diffWaysToCompute(string expression) {
        if(expression.length()==0) return  vector<int>{};
        if(m.find(expression)!=m.end()) return m[expression];
        vector<int>result;
        int num=0;
        int i=0;
        for(i=0;i<expression.length();i++){
            if(expression[i]>='0'&&expression[i]<='9') num=num*10+(expression[i]-'0');
            else break;
        }
        if(i==expression.length()){
            result.push_back(num);
            m[expression]=result;
            return result;
        } 
        for( i=0;i<expression.length();i++){
             if(!(expression[i]>='0'&&expression[i]<='9')){
                 vector<int>result1=diffWaysToCompute(expression.substr(0,i));
                 vector<int>result2=diffWaysToCompute(expression.substr(i+1));
                 for(int j=0;j<result1.size();j++){
                    for(int k=0;k<result2.size();k++){
                        result.push_back(cacluate(result1[j],result2[k],expression[i]));
                    }
                 }
             }
        }
        return result;
    }
    int cacluate(int a,int b,char c){
        if(c=='+') return a+b;
        if(c=='-') return a-b;
        if(c=='*') return a*b;
        return -1;
    }
};