Chemical Formula Parser

You are given a chemical formula as a string. Your task is to compute the total number of atoms of each element in the formula and output the result as a JSON object. The formula may contain nested parentheses, and each element is represented by an uppercase letter optionally followed by a lowercase letter. A number following an element or a closing parenthesis indicates the count of that element or group of elements.

For example, the formula Mg(OH)2 represents one magnesium atom, two oxygen atoms, and two hydrogen atoms, so the output should be {"H":2,"Mg":1,"O":2}.

Please note: The outputs must be printed as JSON objects with the keys sorted in lexicographical order.

Formula Grammar:

• An element is represented as an uppercase letter followed by an optional lowercase letter.
• An element may be followed by a positive integer (if absent, count defaults to 1).
• Parentheses can be used to enclose groups of elements, and a number following the closing parenthesis multiplies the count of each element within the parentheses.

inputFormat

The input consists of a single line containing a non-empty string that represents the chemical formula.

outputFormat

Output a JSON object where each key is an element symbol and the corresponding value is the total count of that element in the formula. The keys in the JSON object must be in lexicographical order.

H2O

{"H":2,"O":1}