<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:
    map<string,int> parser(string& s, int l, int r, map<int,int>& brackets)
    {
        int n=s.length();
        int i=l;
        // cout<<"l r: "<<l<<" "<<r<<"\n";
        map<string,int> m;
        while(i<=r)
        {
            if(s[i]=='(')
            {
                // go till end
                int e=brackets[i];
                string temp;
                int j=i+1;
                while(j<e)
                {
                    temp+=s[j];
                    j++;
                }
                auto curr=parser(s,i+1,e-1,brackets);
                int cnt=0;
                j++;
                while(j<n && s[j]>='0' && s[j]<='9')
                {
                    cnt=cnt*10+(s[j]-'0');
                    j++;
                }
                if(cnt==0)
                    cnt=1;
                for(auto &x:curr)
                {
                    int val=x.second*cnt;
                    m[x.first]+=val;
                }
                i=j;
            }
            else
            {
                assert(s[i]>='A' && s[i]<='Z');
                string temp(1,s[i]);
                int j=i+1;
                while(j<n && s[j]>='a' && s[j]<='z')
                {
                    temp+=s[j];
                    j++;
                }
                int cnt=0;
                if(j==n || !(s[j]>='0' && s[j]<='9'))
                    cnt=1;
                else
                {
                    while(j<n && s[j]>='0' && s[j]<='9')
                    {
                        cnt=cnt*10+(s[j]-'0');
                        j++;
                    }
                }
                m[temp]+=cnt;
                i=j;
            }
        }
        // for(auto &x:m)
        //     cout<<x.first<<"->"<<x.second<<"\n";
        return m;
    }
    string countOfAtoms(string formula) {
        map<int,int> brackets;
        stack<int> s;
        int n=formula.length();
        for(int i=0;i<n;i++)
        {
            if(formula[i]=='(')
                s.push(i);
            else if(formula[i]==')')
            {
                brackets[s.top()]=i;
                s.pop();
            }
        }
        auto ans=parser(formula,0,n-1,brackets);
        string actualAns;
        for(auto &x:ans)
        {
            actualAns+=x.first;
            if(x.second>1)
                actualAns+=to_string(x.second);
        }
        return actualAns;
    }
};
9700