Chemistry

Interview

Time limit1sMemory limit128 MB

Summary

Parse a chemical formula with nested parentheses and multipliers, then output each element's total atom count in lexicographic order.

Level: Medium6 of 10
Topics: Stack, String, Hash map, Recursion
Solved: No attempts yet

Problem

The chemical formula of a molecule M tells us which elements it is made of. A formula follows this grammar.

M := G | M G
G := S | S C
S := A | '(' M ')'
C := T | N E
E := D | D E
T := '2' | ... | '9'
N := '1' | ... | '9'
D := '0' | .. | '9'
A := U | U L | U L L
U := 'A' | .. | 'Z'
L := 'a' | .. | 'z'

The count C multiplies the subgroup S that immediately precedes it.

For example, H2O consists of two H (hydrogen) atoms and one O (oxygen) atom. Likewise, (AlC2)3Na4 consists of 3 Al (aluminium), 6 C (carbon), and 4 Na (sodium) atoms.

Given a chemical formula, write a program that determines which elements make it up.

Input

The input consists of several test cases. Each test case is a single line containing one valid chemical formula, and each line is at most 100 characters long. Input continues until end of file (EOF).

Output

For each test case, print the elements that make up the given formula on one line. Sort the elements in dictionary (lexicographic) order of their symbols, and print each element as its count immediately followed by its symbol, joining consecutive elements with '+'. If an element's count is 1, omit the count.

Examples2

Example 1
Input
```
H2O
(AlC2)3Na4
```
Expected output
```
2H+O
3Al+6C+4Na
```
Example 2
Input
```
C
```
Expected output
```
C
```