# Goodness of a String

Posted: 21 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### For Example:

``````S = “[1, [2, 3], [4, [5, 6] ] ]”
Total depth  = 1*1 + 2*2 + 3*2 + 4*2 + 5*3 + 6*3 = 52
``````

#### Note:

``````1. The given string may be empty.
2. The string will not contain any white spaces.
3. You have to take the modulo with 10 ^ 9 + 7 as the answer may be very large.
``````
##### Input Format:
``````The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case will contain a string ‘S’ which denotes the given nested list.
``````
##### Output Format:
``````For each test case, print a single line containing a single integer denoting the goodness of the given string.

The output for every test case will be printed in a separate line.
``````
##### Note:
``````You don’t need to print anything; It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= |S| <= 100000
1 <= ES[ i ] <= 10^5

Where “|S|” is the length of the given string,  “ES[ i ]” is the element/number stored in the string at the “i-th” position.

Time limit: 1 sec
`````` Approach 1

The basic idea is to traverse through the complete string, make a variable to hold the current depth and whenever found a number just add it into our answer after multiplying it with the current depth.

The steps are as follows:

1. Create two variables “depth” and “ans” to store the current depth and the answer. Initialize both of them with 0.
2. Iterate through ‘s’. (say, iterator = ‘i’)
3. Check if s[ i ] is ‘ , ’ then continue iterations.
4. Else if, s[ i ]  is ‘ [ ‘ which means new depth has started and so, increment “depth” by 1.
5. Else if, s[ i ] is ‘ ] ‘ which means one depth has ended and so, decrement “depth” by 1.
6. Else, there must be a number at s[ i ] and so we have to take all the digits of this number.
• Create a variable “num” that will be going to store the current number.
• Iterate through ‘s’ again. (say, iterator = ‘j’)
• If, s[ j ] becomes equal to ‘ , ‘ or ‘ ] ‘ which means the number has been already picked and so stop the further iterations.
• Else, push this digit into “num”.
• Multiply “num” with “depth” under modulo with 10^9 + 7 and then add the result into the “ans”.
• Set ‘i’ to ‘j’ - 1 as the ‘j’ characters representing the number that has been already picked.
7. Return “ans”.