<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 {
  std::string_view formula_;
  size_t pos_ = 0;

  public:
  Solution() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
  }

  char peek() {
    return pos_ < formula_.length() ? formula_[pos_] : '\0';
  }

  char consume() {
    return pos_ < formula_.length() ? formula_[pos_++] : '\0';
  }

  int32_t parse_count() {
    if (!std::isdigit(peek())) return 1;
    int32_t count = 0;
    while (std::isdigit(peek())) {
      count = count * 10 + (consume() - '0');
    }
    return count;
  }

  std::string parse_atom() {
    std::string atom_name;
    atom_name += consume();
    while (std::islower(peek())) {
      atom_name += consume();
    }
    return atom_name;
  }

  std::map<std::string, int32_t> parse_group() {
    std::map<std::string, int32_t> res;
    while (peek() != ')' && peek() != '\0') {
      if (peek() == '(') {
        consume();
        auto subgroup = parse_group();
        consume();
        int32_t count = parse_count();
        for (const auto &[atom_name, atom_count] : subgroup) {
          res[atom_name] += atom_count * count;
        }
      } else if (std::isupper(peek())) {
        auto atom_name = parse_atom();
        auto count = parse_count();
        res[atom_name] += count;
      } else {
        std::cerr << "wat\n";
      }
    }
    return res;
  }

  std::string countOfAtoms(std::string formula) {
    formula_ = formula;
    pos_ = 0;
    const auto group = parse_group();
    std::string ans;
    for (const auto& [atom, count] : group) {
      ans += atom;
      if (count > 1)
        ans += std::to_string(count);
    }
    return ans;
  }
};

9300