Number of Atoms

Hard

Given a chemical formula (as string s), return the count of each atom. Output the element names in alphabetical order, each followed by its count if the count is greater than 1. Groups may be nested with parentheses and followed by a multiplier.

Example 1

Input:  s = "H2O"
Output: "H2O"

Example 2

Input:  s = "Mg(OH)2"
Output: "H2MgO2"

Example 3

Input:  s = "K4(ON(SO3)2)3"
Output: "K4N3O21S6"

Constraints

• 1 <= s.length <= 16
• s is a valid chemical formula of element tokens, digits, and parentheses.