leetcode: 241. Designing precedence for arithmetic expressions

题目来源

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

题目描述

class Solution {
    
public:
    vector<int> diffWaysToCompute(string expression) {
    

    }
};

题目解析

对于一个形如 x op y（op 为运算符,x 和 y 为数） 的算式而言,它的结果组合取决于 x 和 y 的结果组合数,而 x 和 y 又可以写成形如 x op y 的算式.

因此,该问题的子问题就是x op y中的 x 和 y ：Left and right arithmetic solutions separated by operators

三步：

• 分解：Divided into left and right parts according to the operator,分别求解
• 解决：实现一个递归函数,输入算式,返回算式解
• 合并：根据运算符合并左右两部分的解,得出最终解

class Solution {
    
public:
    vector<int> diffWaysToCompute(string exp) {
    
        vector<int> vec1, vec2, res;
        int N = exp.size();
        int flag = 0;// flag=1说明string是表达式,flag=0说明string是一个数字

        for (int i = 0; i < N; ++i) {
    
            if(exp[i] == '+' || exp[i] == '-' || exp[i] == '*'){
    
                flag = 1;
                vec1 = diffWaysToCompute(std::string(exp, 0, i));
                vec2 = diffWaysToCompute(std::string(exp, i + 1, N - i - 1));
                for(int v1 : vec1){
    
                    for(int v2 : vec2){
    
                        if(exp[i] == '+') res.push_back(v1+v2);
                        if(exp[i] == '-') res.push_back(v1-v2);
                        if(exp[i] == '*') res.push_back(v1*v2);
                    }
                }
            }
        }
        
        if(flag == 0){
    
            return {
    std::stoi(exp)};
        }
        return res;
    }
};