<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:
    def countOfAtoms(self, formula: str) -> str:
        i = 0
        stk = []
        d = defaultdict(int)
        while i < len(formula):
            if formula[i] == '(':
                stk.append(('(', 0))
                i += 1
                continue
            if formula[i] == ')':
                c,i = self.getNumber(formula, i+1)
                # pop all till you get the '(' and multiply by c
                temp = []
                while len(stk) > 0:
                    top = stk[-1]
                    stk.pop()
                    if top[0] == '(':
                        break
                    top1 = (top[0], top[1]*c)
                    temp.append(top1)
                for j in range(len(temp)-1, -1, -1):
                    stk.append(temp[j])
            else:
                e,c, i = self.getItem(formula, i)
                stk.append((e,c))
        for el in stk:
            d[el[0]] += el[1]

        kvs = sorted(list(d.items()))

        r = ""
        for k,v in kvs:
            cnt = str(v) if v > 1 else ""
            r += k+cnt

        return  r


    def getNumber(self, formula: str, i: int):
        '''
        returns next index for the string to consider and the number of immediate repeats
        '''
        num = "" 
        while i < len(formula) and formula[i].isnumeric():
            num += formula[i]
            i += 1
        
        num = '1' if num == "" else num
        return (int(num), i)


    def getItem(self, formula:str, i: int):
        '''
        returns next index for the string to consider and the number of immediate repeats
        '''
        e = formula[i]
        while i < len(formula) - 1 and not formula[i+1].isnumeric() and formula[i+1].islower():
            e += formula[i+1]
            i += 1

        num = "" 
        j = i+1
        while j < len(formula) and formula[j].isnumeric():
            num += formula[j]
            j += 1
        
        num = '1' if num == "" else num
            
        return (e, int(num), j)
        
16800