<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:

  int SearchMultiplier(const string& formula, int start, int* multiplier) {
    int i = start;
    for (; i < formula.length(); ++i) {
      if (!isdigit(formula[i])) {
        break;
      }
    }
    if (i > start) {
      *multiplier = stoi(formula.substr(start, i - start));
    } else {
      *multiplier = 1;
    }
    return i;
  }

  int CountOneAtom(const string& formula, int start, std::unordered_map<string, int>* atom_count) {
    // 'formula[start]' must be a upper-case letter.
    string atom;
    atom.push_back(formula[start]);
    int i = start + 1;
    int multiplier = 1;
    for (; i < formula.length();) {
      const auto& c = formula[i];
      if (islower(c)) {
        atom.push_back(c);
        ++i;
      } else {
        i = SearchMultiplier(formula, i, &multiplier);
        break;
      }
    }
    (*atom_count)[atom] += multiplier;
    return i;
  }
  
  int CountOneBracket(const string& formula, int start, std::unordered_map<string, int>* atom_count) {
    // 'formula[start]' must be a open bracket.
    std::unordered_map<string, int> atom_count_tmp;
    int i = start + 1;
    int multiplier = 1;
    for (; i < formula.length();) {
      const auto& c = formula[i];
      if (c == '(') {
        i = CountOneBracket(formula, i, &atom_count_tmp);
      } else if (isupper(c)) {
        i = CountOneAtom(formula, i, &atom_count_tmp);
      } else if (c == ')') {
        i = SearchMultiplier(formula, i + 1, &multiplier);
        break;
      } else {
        cout << std::format("formula[{}]={} should not happen in CountOneBracket()\n", i, c);
      }
    }
    for (auto& it : atom_count_tmp) {
      (*atom_count)[it.first] += it.second * multiplier;
    }
    return i;
  }

  string countOfAtoms(string formula) {
    std::unordered_map<string, int> atom_count;
    for (int i = 0; i < formula.length();) {
      const auto& c = formula[i];
      if (c == '(') {
        i = CountOneBracket(formula, i, &atom_count);
      } else if (isupper(c)) {
        i = CountOneAtom(formula, i, &atom_count);
      } else {
        cout << std::format("formula[{}]={} should not happen in countOfAtoms()\n", i, c);
      }
    }

    // Sort and output;
    std::map<string, int> atom_count_sorted;
    for (const auto& it : atom_count) {
      atom_count_sorted[it.first] = it.second;
    }
    string output;
    for (const auto& it: atom_count_sorted) {
      if (it.second > 1) {
        output.append(std::format("{}{}", it.first, it.second));   
      } else {
        output.append(it.first);
      }
    }
    return output;
  }
};
12100