Chemical Formula Mass

Interview

Time limit2sMemory limit128 MB

Summary

Parse a chemical formula with nested parentheses and digit multipliers to compute the total atomic mass using H=1, C=12, O=16.

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

Problem

A chemical formula consists of the atom symbols H, C, and O, digits, and parentheses. A digit immediately after an atom tells how many copies of that atom are present; if there is no digit, the count is 1. Every digit is a single digit from 2 through 9.

The same atom may appear several times in one formula. For the calculation, add the masses of all atoms that appear in the formula.

A parenthesized part is treated as one unit. If a digit follows a closing parenthesis, the entire parenthesized unit is repeated that many times. If the parentheses are empty, treat that unit as having mass 0.

The mass of one atom is 1 for hydrogen H, 12 for carbon C, and 16 for oxygen O. Given a chemical formula, compute the sum of the masses of all atoms in it.

Input

The first line contains a chemical formula. The formula is a string made only of H, C, O, (, ), and the digits 2 through 9, and its length does not exceed 100.

Output

Print the formula mass on the first line. No input whose formula mass exceeds 10,000 is given.

Examples3

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