C++ | Recursion with map
Intuition\nTo understand a chemical formula when reading, we take inner most parantheses and resolve outwards from there. Same idea has been used in the impleme
# Intuition\nTo understand a chemical formula when reading, we take inner most parantheses and resolve outwards from there. Same idea has been used in the implementation.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nA recursive strategy can be used in such a way that the formula within a set of parantheses is separately handled by one recursive function. So the approach in this solution uses a recursive function `count`, which maintains its own frequency map `fq` (type is <string, int>), and whenever a \'(\' is observed a recursive call is made. Once a \')\' is noticed, the function checks for any digits following the \')\' which will me multiplied throught the `fq` map and returned.\n\n**Note:** _The recursive function returns a frequency map that contains frequency of each atom appeared within that particular set of parantheses the function handles._\n\n# Complexity\n- Time complexity: $$O(N logN)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    map<string, int> count(string &f, int &p)\n    {\n        map<string,int> fq;\n\n        while(p<f.size())\n        {\n            if(f[p]==\'(\')\n            {\n                ++p;\n                map<string, int> ch = count(f, p);\n                for(auto &el:ch) fq[el.first]+=el.second;\n            }\n            else if(f[p]==\')\')\n            {\n                int l=++p;\n                while(p<f.size() && f[p]>=\'0\' && f[p]<=\'9\') ++p;\n                int cnt=1;\n                if(l<p) \n                {\n                    // cout<<l<<" "<<p<<" - "<<f.substr(l, p-l)<<endl;\n                    cnt=stoi(f.substr(l, p-l));\n                }\n                if(cnt>1)\n                {\n                    for(auto &el:fq) fq[el.first]*=cnt;\n                }\n                break;\n            }\n            else\n            {\n                int l=p++;\n                while(p<f.size() && f[p]>=\'a\' && f[p]<=\'z\') ++p;\n                string atom = f.substr(l, p-l);\n\n                l=p;\n                while(p<f.size() && f[p]>=\'0\' && f[p]<=\'9\') ++p;\n                int cnt=1;\n                if(l<p) \n                {\n                    // cout<<l<<" "<<p<<" - "<<f.substr(l, p-l)<<endl;\n                    cnt=stoi(f.substr(l, p-l));\n                }\n                fq[atom]+=cnt;\n            }\n        }\n\n        return fq;\n    }\n\n    string countOfAtoms(string f) {\n        int ind=0;\n        map<string, int> fq = count(f, ind);\n\n        string ans="";\n        for(auto &pr:fq)\n        {\n            ans+=pr.first;\n            if(pr.second>1) ans+=to_string(pr.second);\n        }\n\n        return ans;\n    }\n};\n```
['Recursion', 'Ordered Map', 'C++']