Score of Parentheses

PROBLEM STATEMENT

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

Approach 2

The idea here is to iterate over the string and for every ‘ith’ character, we check if the character is ‘(‘ or not. If it is found to be true, then we insert the character onto the stack. Else we calculate the score of the inner parentheses and insert double of the score calculated into the stack.

Algorithm:

Initialize a stack ‘S’ to store the current traversed character or the score of inner balanced parenthesis.
Now we iterate the ‘STR’. For every ‘ith’ character we check:
- If the current character is ‘(‘ or not. If found to be true, then we push the current character into the stack ‘S’.
- Else, we check if the top element of the stack is ‘(‘ or not. If found to be true, then insert “1” into the stack which represents the score of the inner balanced parenthesis.
- Otherwise, double the top element of the stack and push the obtained value into the stack ‘S’.
Now return the top element of the stack ‘S’ as the final answer.

Try Problem