<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:
    string countOfAtoms(string formula) {
        stack<string>stk;
        int i = 0;
        while(i<formula.size()){
            if(!stk.empty() && stk.top()==")"){
                stk.pop();
                unordered_map<string,int>m;
                int val = 1;
                while(stk.top()!="("){
                    if(isdigit(stk.top()[0])){
                        val = stoi(stk.top()); 
                    }
                    else{
                        string chem = stk.top();
                        m[chem] += val;
                        val = 1;
                    }
                    stk.pop();
                }
                stk.pop();

                if(isdigit(formula[i])){
                    string digits = "";
                    while(i<formula.size() && isdigit(formula[i])){
                        digits += formula[i];
                        i += 1;
                    }
                    int d = stoi(digits);
                    for(auto it = m.begin(); it!=m.end(); it++){
                        stk.push(it->first);
                        stk.push(to_string(d * it->second));
                    }
                    continue;
                }
                else{
                    for(auto it = m.begin(); it!=m.end(); it++){
                        stk.push(it->first);
                        stk.push(to_string(it->second));
                    }
                }
            }


            if(formula[i]=='(' || formula[i]==')'){
                stk.push(string(1,formula[i]));
                i += 1;
            }
            else if(isdigit(formula[i])){
                string digits = "";
                while(i<formula.size() && isdigit(formula[i])){
                    digits += formula[i];
                    i += 1;
                }
                stk.push(digits);
            }
            else{
                string chem = string(1,formula[i]);
                i += 1;
                while(i<formula.size() && islower(formula[i])){
                    chem += formula[i];
                    i += 1;
                }
                stk.push(chem);
            }
            
        }

        map<string,int>ans;
        int val = 1;
        //cout<<"stack size: "<<stk.size()<<endl;
        while(!stk.empty()){
            if(stk.top()=="(" || stk.top()==")"){
                //do nothing
            }
            else if(isdigit(stk.top()[0])){
                val = stoi(stk.top()); 
            }
            else{
                string chem = stk.top();
                ans[chem] += val;
                val = 1;
            }
            stk.pop();
        }
        string ret = "";
        for(auto it = ans.begin(); it!=ans.end(); it++){
            ret += it->first;
            if(it->second!=1)ret += to_string(it->second);
            //cout<<"ret: "<<ret<<endl;
        }
        return ret;
    }
};
11800