New update is available. Click here to update.

Last Updated: 4 Nov, 2020

Moderate

```
The given formula consists of English alphabets, digits, β(β and β)β.
The given formula is always valid.
```

```
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.
The only line of each test case contains a string representing the formula.
```

```
For each test case, return the string representing the count of all the elements is printed.
The output for each test case is in a separate line.
```

```
You are not required to print the expected output, it has already been taken care of. Just implement the function.
```

```
1 <= T <= 10
1 <= |S| <= 10^4
Time Limit: 1 sec
```

```
The count of each element in the formula will not exceed 2^31.
```

Approaches

The main idea behind this approach is to use recursion and find the count of atoms between a β(β and a β)β. Whenever we encounter a β(β, we make a recursive call to the function, which after execution, gives an unordered map consisting of the count of atoms within the current formula. Then, we can use that map to calculate the count of atoms in a string containing that parenthesis.

Following is the algorithm for this approach :

- If we encounter alphabets/atoms, then add them to a string. If any lowercase letters follow, then append them to the string as well.
- If we encounter digits, then build the total value of the current number.
- After processing the alphabet and digit, add it to a UNORDERED_MAP<STRING, INT>
- If the Atom already exists in the map then add the digit to the existing value else just insert the atom with the digit.
- If we encounter '(' then recursively call the function with a new UNORDERED_MAP<STRING, INT> and repeat steps 1 to 4.
- Once we return from the recursive call process with the new map, add its <ATOM, VALUE> pairs to the existing map.
- Whenever we encounter ')', we will check if there is a digit following ')'. If yes, then we multiply that digit with all the values in the map.
- Now, we have the count of each element in the final map. Push all the elements and their respective counts from the map to a vector/list/array. Since we need the elements in sorted order, we sort these elements and then build a string from the final sorted structure.

The main idea behind this approach is to use STACK and solve the problem iteratively. We store the current value of the numeric counter the STACK whenever we encounter a β)β. The value of the numeric counter indicates the count of the current element.

We use two variables:

- CNT: to denote the current value of the numeric counter i.e. the count of the current element. This variable is initialized to 0.
- COEFF: indicates the value by which the multiplicities of the elements between a pair of brackets should be increased. This variable is initialized to 1.

We start traversing the formula from right to left and do the following :

- If the character is a digit, include it in the variable CNT
- If the character is a β)β, multiply the variable COEFF by the value stored in CNT (if CNT is not equal to 0). Also, push the value of CNT onto the STACK (or we push 1 if the value of CNT is 0) and set the value of CNT to 0 again.
- If the character is a β(β, we won't multiply the following elements with the last numeric counter, so pop the last value of CNT and divide the variable COEFF by this last value.
- If the character is an uppercase alphabet, add the character to the current element. Also, we have to add the element and its count (given by COEFF * CNT) to the dictionary. If the value of the variable CNT is 0, the count of the element will be COEFF * 1 i.e. COEFF. We also reset the value of CNT to 0.
- If the character is a lowercase alphabet, just add the character to the current element.

After the traversal, return the string formed by joining the sorted key and value pairs in the map.