Python | Stack-Based Parsing
see the Successfully Accepted Submission\n\n# Code\n\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n        # Stack to hold the current lev
[see the Successfully Accepted Submission](https://leetcode.com/problems/number-of-atoms/submissions/1320481151/?envType=daily-question&envId=2024-07-14)\n\n# Code\n```\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n        # Stack to hold the current level of counts\n        stack = [Counter()]\n        i = 0\n        n = len(formula)\n        \n        while i < n:\n            if formula[i] == \'(\':\n                # Start a new level of counts\n                stack.append(Counter())\n                i += 1\n            elif formula[i] == \')\':\n                # End the current level of counts\n                i += 1\n                # Find the multiplier\n                start = i\n                while i < n and formula[i].isdigit():\n                    i += 1\n                multiplier = int(formula[start:i] or 1)\n                # Pop the current level and merge it into the previous level\n                top = stack.pop()\n                for elem, count in top.items():\n                    stack[-1][elem] += count * multiplier\n            else:\n                # Read the element name\n                start = i\n                i += 1\n                while i < n and formula[i].islower():\n                    i += 1\n                elem = formula[start:i]\n                # Read the number\n                start = i\n                while i < n and formula[i].isdigit():\n                    i += 1\n                count = int(formula[start:i] or 1)\n                # Add the count to the current level\n                stack[-1][elem] += count\n        \n        # The final counts are in the last item on the stack\n        result = stack.pop()\n        # Sort by element names\n        sorted_elements = sorted(result.items())\n        # Build the output string\n        output = []\n        for elem, count in sorted_elements:\n            output.append(elem)\n            if count > 1:\n                output.append(str(count))\n        \n        return \'\'.join(output)\n        \n```\n\n## Approach the Problem Step-by-Step\n\n1. **Parsing Elements**: Identify elements which start with an uppercase letter and may be followed by one or more lowercase letters.\n2. **Handling Multipliers**: If an element is followed by a digit, the digit indicates the count of that element. If no digit follows, the count is 1.\n3. **Parentheses Handling**: Handle nested parentheses by using a stack to manage scope. When a closing parenthesis is encountered, we need to multiply the counts of the contained elements by the subsequent digit.\n4. **Combining Results**: Merge all counts from different scopes and finally produce a sorted result based on element names.\n\n## Explanation of the Code\n\n1. **Stack Usage**: We use a stack to manage nested counts of atoms. Each level of nested parentheses pushes a new `Counter` onto the stack.\n2. **Reading Elements and Counts**: The code identifies elements by their capital letters followed by optional lowercase letters and reads subsequent digits to determine their counts.\n3. **Handling Parentheses**: When encountering a closing parenthesis, the top `Counter` is popped, its counts are multiplied by the found multiplier, and the results are merged into the previous level.\n4. **Final Assembly**: After processing the entire formula, the resulting counts are sorted and formatted into the desired output string.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']