Count Atoms in a Chemical Formula
A parser must expand a chemical formula with nested parentheses and multipliers into a sorted count of each element — a clean stress test for recursive-descent or stack-based parsing.
Problem
Given a string formula representing a chemical formula, return the count of each atom. The formula contains element names (an uppercase letter optionally followed by lowercase letters), optional counts, and parenthesized groups with optional multipliers. Output the elements in sorted order, each followed by its count if greater than 1, concatenated with no spaces.
Input
A string formula of length [1, 1000] that is a valid chemical formula.
Output
A string: element names in alphabetical order, each followed by its total count if > 1.
Constraints
- 1 <= formula.length <= 1000
- Element names start with an uppercase letter, optionally followed by lowercase letters.
- All counts are positive integers (absent means 1).
Examples
Example 1
Input
formula = "H2O"
Output
"H2O"
2 H atoms and 1 O atom.
Example 2
Input
formula = "K4(ON(SO3)2)2"
Output
"K4N2O14S4"
Nested multipliers expand and sum per element.