<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 ll = long long int;
   string countOfAtoms(string s) {
      int n = s.length();
      string fr = "";
      string number = "";
      ll tot_multi = 1;
      ll multi = 1;
      bool Number = false;
      vector < ll > pos;
      map < string, ll > cnt;

      for (int i = n - 1; i >= 0; i--) {
         if (isdigit(s[i])) {
            Number = true;
            number.push_back(s[i]);
         }
         if (s[i] == ')') {
            if (Number) {
               reverse(number.begin(), number.end());
               tot_multi *= stoll(number);
               pos.push_back(stoll(number));
               Number = false;
               number = "";
            } else {
               pos.push_back(1);
            }

         }
         if (s[i] == '(') {
            if (!pos.empty()) {
               tot_multi /= * pos.rbegin();
               pos.pop_back();
            }
         }
         if ((0 <= s[i] - 'a') && (s[i] - 'a' <= 26)) {
            if (Number) {
               reverse(number.begin(), number.end());
               multi *= stoll(number);
               number = "";
               Number = false;
            }
            fr.push_back(s[i]);
         } else if ((0 <= s[i] - 'A') && (s[i] - 'A' <= 26)) {
            ll local = 1;
            fr.push_back(s[i]);
            reverse(fr.begin(), fr.end());
            if (Number) {
               reverse(number.begin(), number.end());
               multi *= stoll(number);
               Number = false;
               number = "";
            }
            if (multi != 1) {
               local *= multi;
               multi = 1;
            }
            local *= tot_multi;
            cnt[fr] += local;
            fr = "";
         }
      }

      string res = "";
      // deb(cnt);
      for (auto & i: cnt) {
         res += i.first;
         if (i.second == 1) {
            continue;
         }
         res += to_string(i.second);
      }
      return res;
   }

};
8800