# https://leetcode.com/problems/number-of-atoms
from typing import Dict, List

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        s: List[Dict[str, int]] = [{}]
        idx = 0
        while idx < len(formula):
            if formula[idx] == ')':
                idx += 1
                mul = 0
                while idx < len(formula) and formula[idx].isdecimal():
                    mul = mul * 10 + int(formula[idx])
                    idx += 1
                if mul == 0:
                    mul = 1
                d = s.pop()
                for key in d:
                    s[-1][key] = s[-1].get(key, 0) + (d[key] * mul)
                continue
            if formula[idx] == '(':
                s.append({})
                idx += 1
                continue
            key = ''
            if formula[idx].isalpha():
                key += formula[idx]
                idx += 1
                while idx < len(formula) and formula[idx].islower():
                    key += formula[idx]
                    idx += 1
            cnt = 0
            while idx < len(formula) and formula[idx].isdecimal():
                cnt = cnt * 10 + int(formula[idx])
                idx += 1
            if cnt == 0:
                cnt = 1
            s[-1][key] = s[-1].get(key, 0) + cnt
        return ''.join(key + (str(v) if v > 1 else '') for key, v in sorted(s[-1].items()))