<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 merge(const map<string, int>& m1, map<string, int>& m2){
        for (const auto& [k, v] : m1){
            m2[k] += v;
        }
    }
    void multiply(map<string, int>& m, int factor){
        for (auto& [k, v] : m){
            m[k] *= factor;
        }
    }
    pair<int, int> read_int(const string& s, int start){
        int out = 0;
        while (start < s.size() && isdigit(s[start])){
            out *= 10;
            out += stoi(string(1, s[start]));
            start++;
        }
        return make_pair(out, start);
    }
    pair<map<string, int>, int> count(const string& s, int start){
        map<string, int> out;
        bool parsing_name = false;
        string name = "";
        for (int i = start; i < s.size(); i++){
            if (s[i] == '('){
                if (parsing_name){
                    out[name] += 1;
                    name = "";
                    parsing_name = false;
                }
                auto res = count(s, i+1);
                merge(res.first, out);
                i = res.second-1;
            } else if (s[i] == ')'){
                if (parsing_name){
                    out[name] += 1;
                    name = "";
                    parsing_name = false;
                }
                auto res = read_int(s, i+1);
                if (res.first == 0){
                    multiply(out, 1);
                } else {
                    multiply(out, res.first);
                }
                return make_pair(out, res.second);
            } else if (!isdigit(s[i]) && isupper(s[i])){
                if (!parsing_name){
                    parsing_name = true;
                    name += s[i];
                } else {
                    out[name] += 1;
                    name = "";
                    name += s[i];
                }
            } else if (parsing_name && !isdigit(s[i]) && !isupper(s[i])){
                name += s[i];
            } else if (parsing_name && isdigit(s[i])){
                parsing_name = false;
                auto res = read_int(s, i);
                i = res.second-1;
                out[name] += res.first;
                name = "";
            }
        }
        if (parsing_name){
            out[name] += 1;
        }
        return make_pair(out, s.size());
    }
    string countOfAtoms(string formula) {
        auto res = count(formula, 0);
        string output = "";
        for (const auto& [k, v] : res.first){
            output += k;
            if (v != 1) output += to_string(v);
        }
        return output;
    }
};
11100