Count how many atoms of each element occur in the valid chemical formula. Return the element names in lexicographic order, appending each total count when it is greater than 1. Do not append a count of 1.
An element name starts with an uppercase English letter and may continue with lowercase English letters. A decimal count after an element multiplies that element; a count after a parenthesized group multiplies everything in the group. Missing counts mean 1. Groups may be nested, and adjacent elements or groups are combined.
Explicit counts are greater than 1. Each final element count fits in a signed 32-bit integer.
Example 1:
Input: formula = "Ca(OH)2"
Output: "CaH2O2"Explanation: The group OH occurs twice, giving two O atoms and two H atoms, plus one Ca atom. In lexicographic order the result is CaH2O2.
Example 2:
Input: formula = "Al2(SO4)3"
Output: "Al2O12S3"Explanation: There are two Al atoms. Multiplying the SO4 group by 3 gives three S atoms and twelve O atoms. Sorting the element names gives Al2O12S3.
Example 3:
Input: formula = "NaClNa"
Output: "ClNa2"Explanation: Na appears twice and Cl appears once. Cl comes before Na lexicographically, so the result is ClNa2.
Constraints:
1 <= formula.length <= 1000- The formula contains English letters, decimal digits, and parentheses.
- The formula is valid under the rules above.
- Each element's final count is at most
2147483647.