<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:
    using int3 = array<int, 3>; // (pos for right ')', real ending, multiplier)
    vector<int3> mult;
    int n;
    int atom[702]; // Array to store counts of each atom

    // Convert chemical formula string to index
    inline int idx(string& s) {
        return (s[0] - 'A') * 27 + ((s.size() == 1) ? 0 : (s[1] - 'a' + 1));
    }

    // Convert index to chemical formula string
    inline string chemi(int x) {
        auto [q, r] = div(x, 27);
        string s = string(1, q + 'A');
        if (r > 0)
            s += (r - 1 + 'a');
        return s;
    }

    // Recursive function to count atoms
    void f(int i, string& formula, int l = -1, int r = -1, int times = 1) {
        while (i < r) {
            if (formula[i] == '(') {
                auto& m = mult[i];
                f(i+1, formula, i+1, m[0], m[2] * times);
                i = m[1] + 1;
            } 
            else if (isupper(formula[i])) {
                string chemi = string(1, formula[i]);
                int start = i;
                if (i+1 < r && islower(formula[i+1])) {
                    chemi+= formula[i+1];
                    i++;
                }
                i++;

                int x = 0;
                while (i < r && isdigit(formula[i])) {
                    x=x*10 + (formula[i]-'0');
                    i++;
                }
                if (x== 0) x= 1;
                atom[idx(chemi)]+= x* times;
            } 
            else 
                i++;
        }
    }

    // Convert atom array to result string
    inline string convert() {
        string result;
        for (int i = 0; i < 702; ++i) {
            if (atom[i] > 0) {
                result += chemi(i);
                if (atom[i] > 1)
                    result += to_string(atom[i]);
            }
        }
        return result;
    }

    string countOfAtoms(string& formula) {
        memset(atom, 0, sizeof(atom));
        n=formula.size();

        vector<int> st;
        mult.assign(n, {-1, -1, -1});
        for (int i = 0; i < n; i++) {
            char c = formula[i];
            if (c == '(')
                st.push_back(i);
            else if (c == ')') {
                int x = 0, r = i;
                while (i + 1 < n && isdigit(formula[i + 1])) {
                    x = 10 * x + (formula[++i] - '0');
                }
                if (x == 0)
                    x = 1;
                int l = st.back();
                st.pop_back();
                mult[l] = {r, i, x};
            }
        }
        f(0, formula, 0, n, 1); // Start recursive function
        return convert();       // Convert the atom array to result string
    }

};

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
8400