<p>Given a string <code>formula</code> representing a chemical formula, return <em>the count of each atom</em>.</p>

<p>The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.</p>

<p>One or more digits representing that element&#39;s count may follow if the count is greater than <code>1</code>. If the count is <code>1</code>, no digits will follow.</p>

<ul>
	<li>For example, <code>&quot;H2O&quot;</code> and <code>&quot;H2O2&quot;</code> are possible, but <code>&quot;H1O2&quot;</code> is impossible.</li>
</ul>

<p>Two formulas are concatenated together to produce another formula.</p>

<ul>
	<li>For example, <code>&quot;H2O2He3Mg4&quot;</code> is also a formula.</li>
</ul>

<p>A formula placed in parentheses, and a count (optionally added) is also a formula.</p>

<ul>
	<li>For example, <code>&quot;(H2O2)&quot;</code> and <code>&quot;(H2O2)3&quot;</code> are formulas.</li>
</ul>

<p>Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than <code>1</code>), followed by the second name (in sorted order), followed by its count (if that count is more than <code>1</code>), and so on.</p>

<p>The test cases are generated so that all the values in the output fit in a <strong>32-bit</strong> integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> formula = &quot;H2O&quot;
<strong>Output:</strong> &quot;H2O&quot;
<strong>Explanation:</strong> The count of elements are {&#39;H&#39;: 2, &#39;O&#39;: 1}.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> formula = &quot;Mg(OH)2&quot;
<strong>Output:</strong> &quot;H2MgO2&quot;
<strong>Explanation:</strong> The count of elements are {&#39;H&#39;: 2, &#39;Mg&#39;: 1, &#39;O&#39;: 2}.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> formula = &quot;K4(ON(SO3)2)2&quot;
<strong>Output:</strong> &quot;K4N2O14S4&quot;
<strong>Explanation:</strong> The count of elements are {&#39;K&#39;: 4, &#39;N&#39;: 2, &#39;O&#39;: 14, &#39;S&#39;: 4}.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= formula.length &lt;= 1000</code></li>
	<li><code>formula</code> consists of English letters, digits, <code>&#39;(&#39;</code>, and <code>&#39;)&#39;</code>.</li>
	<li><code>formula</code> is always valid.</li>
</ul>

class Solution {
public:
    void count_atoms(string &formula,map<string,long long> &frequency_map){
         int n=formula.size(),i=0;
         string atom,count;
         while(i<n){
            if(isalpha(formula[i])){
                if(isupper(formula[i])){
                    if(atom.size()!=0){
                        long long frequency=1;
                        if(count.size()!=0) frequency=stoi(count);
                        frequency_map[atom]+=frequency;
                    }
                    atom.clear();
                    count.clear();
                    atom.push_back(formula[i]);
                }
                else{
                    atom.push_back(formula[i]);
                }
            }
            else if(isdigit(formula[i])){
                count.push_back(formula[i]);
            }
            else{
                if(atom.size()!=0){
                    long long frequency=1;
                    if(count.size()!=0) frequency=stoi(count);
                    frequency_map[atom]+=frequency;
                }
                atom.clear();
                count.clear();
                int j=i+1,c=1;
                string new_formula;
                while(j<n && c!=0){
                    if(formula[j]=='(') c++;
                    else if(formula[j]==')') c--;
                    new_formula.push_back(formula[j]);
                    j++;
                }
                new_formula.pop_back();
                cout<<new_formula<<endl;
                map<string,long long> new_frequency_map;
                count_atoms(new_formula,new_frequency_map);
                i=j;
                while(i<n && isdigit(formula[i])){
                    count.push_back(formula[i]);
                    i++;
                }
                i--;
                cout<<count<<endl;
                long long frequency=1;
                if(count.size()!=0) frequency=stoi(count);
                for(auto it:new_frequency_map){
                    string ele=it.first;
                    cout<<ele<<" "<<new_frequency_map[ele]<<endl;
                    new_frequency_map[ele]*=frequency;
                }
                cout<<"___________________________________________________________________"<<endl;
                for(auto it:new_frequency_map){
                    string ele=it.first;
                    if(frequency_map.find(ele)==frequency_map.end()) frequency_map[ele]=new_frequency_map[ele];
                    else frequency_map[ele]+=new_frequency_map[ele];
                }
            }
            i++;
         }
         if(atom.size()!=0){
             long long frequency=1;
             if(count.size()!=0) frequency=stoi(count);
             frequency_map[atom]+=frequency;
         }
    }
    string countOfAtoms(string formula) {
        int n=formula.size();
        map<string,long long> frequency_map;
        if(formula[0]=='(' && formula[n-1]==')'){
            formula.erase(n-1,1);
            formula.erase(0,1);
        }
        count_atoms(formula,frequency_map);
        string final_formula;
        for(auto x:frequency_map){
            string count;
            if(x.second>1) count=to_string(x.second);
            final_formula=final_formula+x.first+count;
        }
        return final_formula;
    }
};
11700