Molecular Mass

Interview

Time limit1sMemory limit128 MB

Summary

Parse a nested chemical formula with parentheses and repeat counts, then compute the total molecular mass from atomic weights.

Level: Medium4 of 10
Topics: Stack, Recursion, String
Solved: No attempts yet

Problem

A molecule can be described as a sequence of atoms and written as a chemical formula made of letters that denote those atoms. For example, H denotes an atom of hydrogen, C denotes an atom of carbon, and O denotes an atom of oxygen. The formula COOH represents a molecule made of one carbon atom, two oxygen atoms, and one hydrogen atom.

To write formulas more compactly, the following rules are used.

Letters that denote atoms can be grouped by enclosing them in parentheses; for example, the formula CH(OH) contains the group OH. Groups can be nested, so a group may itself contain other groups. To shorten a formula, consecutive occurrences of the same letter can be replaced by that letter followed by the count of occurrences. For example, COOHHH can be written as CO2H3, and it represents a molecule made of one carbon atom, two oxygen atoms, and three hydrogen atoms.

Likewise, consecutive occurrences of the same group can be replaced by that group followed by the count of occurrences. For example, CH(CO2H)(CO2H)(CO2H) can be written as CH(CO2H)3; the molecule that both formulas describe consists of four carbon atoms, four hydrogen atoms, and six oxygen atoms.

A number written after a letter or a group is always at least 2 and at most 9.

The mass of a molecule is the sum of the masses of all its atoms. One hydrogen atom has mass 1, one carbon atom has mass 12, and one oxygen atom has mass 16.

Write a program that computes the mass of a molecule.

Input

The single line of input contains the formula of the molecule whose mass must be determined. The formula consists only of the characters H, C, O, (, ), and the digits 2, 3, ..., 9. Its length is at most 100 characters.

Output

Print a single line containing the mass of the molecule described by the given formula. The result is always at most 10,000.

Examples4

Example 1
Input
```
COOH
```
Expected output
```
45
```
Example 2
Input
```
CH(CO2H)3
```
Expected output
```
148
```
Example 3
Input
```
((CH)2(OH2H)(C(H))O)3
```
Expected output
```
222
```
Example 4
Input
```
H
```
Expected output
```
1
```