<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 {
private:
    void _countOfAtoms(string& formula, int& idx, int sub, map<string, int>& tbl) {
        int i;
        int num;
        map<string, int>::iterator it;

        num = sub;
        while (idx >= 0) {
            char c;
            string nm;

            c = formula[idx];
            // cout << c << endl;
            if (isalpha(c)) {
                for (i = idx; !isupper(formula[i]); i--)
                    ;
                nm = string(begin(formula) + i, begin(formula) + idx + 1);
                it = tbl.find(nm);
                if (it == end(tbl)) {
                    tbl[nm] = num;
                    // cout << nm << " -> " << num << endl;
                } else {
                    it->second += num;
                    // cout << nm << " -> " << it->second << endl;
                }
                num = sub;
                idx = i - 1;
            } else if (isdigit(c)) {
                int pow;
                int val;

                val = c - '0';
                pow = 10;
                for (i = idx - 1;; i--) {
                    c = formula[i];
                    if (!isdigit(c))
                        break;
                    val += pow * (c - '0');
                    pow *= 10;
                }
                idx = i;
                // cout << "Parsed " << val << endl;
                num = sub * val;
                // cout << "Subscript " << num << endl;
            } else if (c == '(') {
                --idx;
                return;
            } else if (c == ')') {
                --idx;
                _countOfAtoms(formula, idx, num, tbl);
                num = sub;
            }
        }
    }

public:
    string countOfAtoms(string formula) {
        int idx;
        map<string, int> tbl;
        map<string, int>::iterator it;
        string res;

        idx = formula.length() - 1;

        _countOfAtoms(formula, idx, 1, tbl);

        for (it = begin(tbl); it != end(tbl); ++it) {
            res += it->first;
            if (it->second > 1)
                res += to_string(it->second);
        }

        return res;
    }
};
8600