Score of Parentheses

Posted: 27 Apr, 2021
Difficulty: Moderate


Try Problem

One day Ninja goes to play some intellectual games. There was a game where Ninja is given a string of balanced parentheses 'STR' and he has to calculate the score of that using the given rules of the game. If he wins that game, the amount which he has paid for that game will be refunded.

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.

Your task is to find the score using these rules for the given string 'STR'.

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’.
Try Problem