C++ long Fu... recursion,


  • 0
    G
    class Solution {
    public:
        
        void getCountOfAtoms(const string &formula, int &idx, map<string,int> &m){
            if(idx >= formula.size()){
                return;
            }
            
            if(formula[idx] == '(') {
                idx++;
                map<string,int> newMap;
                getCountOfAtoms(formula,idx,newMap);
                
                for(auto &p : newMap){
                    
                    m[p.first] += p.second;
                    cout << p.first << m[p.first] << endl;
                }        
                
                getCountOfAtoms(formula,idx,m);
                return;
            }
            
            if(formula[idx] == ')'){
            
                string scount;
                int count = 0;
                idx++;
                
                while(idx != formula.size() && isdigit(formula[idx])){
                    scount.push_back(formula[idx++]);    
                }
                
                if(scount.empty()){
                    count = 1;
                }
                else{
                    istringstream ss(scount);
                    ss >> count;
                }
                
                for(auto &p : m){
                    p.second *= count;
                    cout << p.first << " " << p.second << endl;
                }
                
                return;
            }
            
            bool foundElm = false;
            string currElm;
            while(isalpha(formula[idx])){
                if(isupper(formula[idx])){
                    if(foundElm){
                        break;
                    }
                    
                    foundElm = true;
                }
                
                currElm.push_back(formula[idx]);
                idx++;
            }
            
            string count;
            while(idx != formula.size() && isdigit(formula[idx])){
                count += formula[idx];
                idx++;
            }
            
            int numCount = 0;
            
            if(count.empty()){
                numCount = 1;
            }
            else{
                istringstream ss(count);
                ss >> numCount;
            }
            
            m[currElm] += numCount;
            getCountOfAtoms(formula,idx,m);
        }
        
        string makeString(map<string,int> &m){
            string result;
            for(auto &p : m){
                result += p.first;
                
                if(p.second > 1){
                    ostringstream ss;
                    ss << p.second;
                    result += ss.str();
                }
            }
            
            return result;
        }
        
        string countOfAtoms(string formula) {
            int i = 0;
            map<string,int> counter;
            getCountOfAtoms(formula,i,counter);
            return makeString(counter);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.