287. Number of Atoms

Given a chemical formula (as a string), return the count of each element. Output the formula with element names in alphabetical order, each followed by its count if greater than one (counts of one are omitted). Formulas may contain parentheses with multipliers.

Input: A quoted chemical formula.

Output: Quoted string — the canonical count formula.

Examples

Input: "H2O"
Output: "H2O"
Explanation: 2 H, 1 O.

Input: "Mg(OH)2"
Output: "H2MgO2"
Explanation: H2, Mg1, O2 sorted.

Input: "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
Explanation: Expanded and sorted.

Constraints

• 1<=formula.length<=1000
• valid chemical formula

Asked by