# Score of Parentheses

Posted: 27 Apr, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Rules for the game are as follows:

``````For “()” you get a score of 1.
For “x y” you get a score of x + y where x and y are individual pairs of balanced parentheses.
For “(x)” you get a score twice of x (i.e), 2 * score of x.
``````

#### Example :

``````Suppose given string 'STR' is “( ( ) )”.
So we return ‘2’ as input is of the form “(x)”, therefore total score = 2 * score of “()” = 2 * 1 = 2.
``````
##### Note :
``````You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
``````

#### Input Format :

``````The first line of input contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ representing the length of the string.

The second line of each test case contains a string ‘STR’ containing the balanced parentheses.
``````

#### Output Format :

``````For each test case, return the score of the string using the rules given.
``````

#### Constraints :

``````1 <= T <= 50
1<= |STR| <= 1000
STR[I] = { ‘(‘, ‘)’ }

Where ‘T’ represents the number of test cases and ‘STR’ represents the given string.

Time Limit: 1 second
`````` Approach 1

The idea here is to use the recursion. If we encounter any ‘(‘ bracket and then ‘)’ bracket, we simply increase the score. Else if we found another ‘(‘ bracket, we call the recursively the same function and multiply the output by ‘2’ as for the nested parenthesis like ‘( ( ) )’, the answer will be 2 * score. In this way, we proceed to get our final answer.

• We make a new function helper which takes input ‘STR’, ‘N’, and a variable ‘i’ which is passed as a reference.
• Now we call this function. In this function we :
• Run a loop while ‘i’  < length('STR').
• Now we check:
• If ‘STR[i] == ‘(‘
• If ‘STR[++i] == ‘)’
• ‘ANS++’
• i++
• Else we call our recursive function as nested parenthesis like ‘( ( ) )’ can be there and multiply the score obtained by 2.
• ANS = ANS + 2 * helper(STR, N , i)
• Else
• Return ‘ANS’.