分治算法为运算表达式设计优先级

今天药忘吃喽~ 2023-01-01 15:59 135阅读 0赞

# 本算法是基于分治思想进行实现 #

## 思路 ##

##### 首先对字符串进行预处理，将数字和运算符进行分开存储，然后便可以继续分治策略。 #####

##### 基本分治策略大概如下： #####

我们假设数字的数目为n，然后将前m个数字求出他们的所有优先级的结果，然后求出后n-m个数字的所有优先级的结果。做完这两步之后找到前m个数和后n-m个数中间隔的算数符号，然后用这个算数符号对这两组数据的结果进行运算。其中m一直从1迭代到n-1即可解除所有解的答案。  
此外，在本题中回顾了一下分治算法，其有一特点是直到分治的可以问题足够小以至于我们可以用`if` `else`去进行解答的时候便可以不在进行分解。在此问题中可以分解到数字的个数为2我们可以直接求出结果。也可以分解为数字的个数为1这样我们可以直接返回结果，本人认为两种都属于本题目问题的可直接解决范围。

##### 贴代码： #####

class Solution {
        
    public:
        vector<int> diffWaysToCompute(string input) {
        
            //采用深度优先或者动态规划
            //首先对字符串进行处理
            vector<int> nums;
            vector<char> cs;
            int num=0;
            for(int i=0;i<input.size();i++){
        
                char c=input[i];
                if(c>='0' && c<='9'){
        
                    num=num*10+(c-'0');
                }
                else{
        
                    cs.push_back(c);
                    nums.push_back(num);
                    num=0;
                }
                if(i==input.size()-1) {
        
                    nums.push_back(num);
                }
            }
            return total(nums,cs,0,nums.size());
        }
        vector<int> total(vector<int> nums,vector<char> cs,int index_num,int n){
        
            if(n==1) return {
        nums[index_num]};
            vector<int> res;
            vector<int> res1;
            vector<int> res2;
            for(int i=1;i<n;i++){
        
                res1=total(nums,cs,index_num,i);
                res2=total(nums,cs,index_num+i,n-i);
                for(auto num1:res1){
        
                    for(auto num2:res2){
        
                        switch(cs[index_num+i-1]){
        
                            case '+': res.push_back(num1+num2);
                            break;
                            case '-':res.push_back(num1-num2);
                            break;
                            case '*':res.push_back(num1*num2);
                            break;
                        }
                    }
                }
            }
            return res;
        }
    };