A reagent bottle's label gives its chemical formula as the string formula. It is built from:
- an element: one uppercase letter followed by zero or more lowercase letters (
H,Mg,Uue), optionally followed by a count; - a group: a formula wrapped in
(and), optionally followed by a count that multiplies everything inside it.
A count is a positive integer written with one or more digits; a missing count means 1.
Return a dictionary mapping every element name that appears to its total number of atoms.
The order of the keys does not matter. Return {} for an empty formula.
Examples
Input: formula = "H2O"
Output: {'H': 2, 'O': 1}
Input: formula = "Mg(OH)2"
Output: {'Mg': 1, 'O': 2, 'H': 2}
Input: formula = "K4(ON(SO3)2)2"
Output: {'K': 4, 'O': 14, 'N': 2, 'S': 4}
Explanation: inside the outer group, O appears 1 + 3 * 2 = 7 times; doubled, 14.
Constraints
0 <= len(formula) <= 2 * 10**5; the formula is always well formed and groups are never empty- Groups can be nested up to 3000 levels deep, and totals can be astronomically large
- Target: time roughly proportional to the length of the formula
Goals
- Tokenise element names and multi-digit counts by scanning characters
- Use a stack of tallies, one per open group, and fold a group into its parent when it closes
- Avoid expanding repeated groups as text, which grows exponentially