```
#include <bits/stdc++.h>
int ninjaParentheses(string s, int n) {
int ans=0;
stack<int> st;
for(auto x: s) {
if(x=='(') {
st.push(ans);
ans=0;
} else {
ans=st.top()+max(2*ans, 1);
st.pop();
}
}
return ans;
}
```

Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.
```

```
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
```

Detailed explanation

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
```

```
2
4
()()
6
(()())
```

```
2
4
```

```
Test Case 1 :
For the first test case, the given string 'STR' is “( ) ( )”. As 'STR' is in the form 'x + y', so we return ‘2’ as the score we get is 1 + 1 = 2.
Test Case 2 :
For this test case, the given string 'STR' is “( ( ) ( ) )”. So we return ‘4’ as the score we get is 2 * ( 1 + 1 ) = 4 as it is in the form '(x + y)'.
```

```
2
2
()
8
(()(()))
```

```
1
6
```

```
Test Case 1 :
For the first test case, the given string 'STR' is “( )”. So we return ‘1’ as only one balanced parenthesis is present.
Test Case 2 :
For this test case, the given string 'STR' is “( ( ) ( ( ) ) )”. As 'STR' is in the form '( x + ( y ) )', so we return ‘6’ as the score we get is 2 * ( 1 + 2 * (1) ) = 6.
```

Hint

Can you think of a recursive approach?

Approaches

Recursive Approach

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)

- ANS = ANS + 2 *

- If ‘STR[++i] == ‘)’
- Else
- Return ‘ANS’.

- If ‘STR[i] == ‘(‘

- Now we check:

Time Complexity

O(N), where ‘N’ is the size of the string.

As we are iterating through our string one time so complexity becomes O(N) time.

Space Complexity

O(N), where ‘N’ is the size of the string.

As recursion uses a stack space of size ‘N’ for storing recursive calls.

Code Solution

(100% EXP penalty)

Score of Parentheses

All tags

Sort by

Interview problems

C++ || Easy Solution

```
#include <bits/stdc++.h>
int ninjaParentheses(string s, int n) {
int ans=0;
stack<int> st;
for(auto x: s) {
if(x=='(') {
st.push(ans);
ans=0;
} else {
ans=st.top()+max(2*ans, 1);
st.pop();
}
}
return ans;
}
```

50 views

0 replies

0 upvotes

Interview problems

Java Solution

```
import java.util.* ;
import java.io.*;
public class Solution {
public static int ninjaParentheses(String str, int n) {
// Write your code here.
Stack<Integer> st = new Stack<>();
for(int i = 0; i < n ; i++){
char ch = str.charAt(i);
if(ch == '(')st.push(0);
else if(ch == ')'){
if(st.peek() == 0){
st.pop();
st.push(1);
}else{
int sum =0;
while(st.peek() != 0){
sum += st.pop();
}
st.pop();
st.push(2*sum);
}
}
}
int res = 0;
while(!st.isEmpty()){
res += st.pop();
}
return res;
}
}
```

22 views

0 replies

0 upvotes

Interview problems

c++ solution

#include <bits/stdc++.h>

int ninjaParentheses(string str, int n)

{

// Write your code here.

int depth = 0, res = 0;

char prev = '(';

for (char ch: str) {

if (ch == '(')

depth++;

else {

depth--;

if (prev == '(')

res += pow(2, depth);

}

prev = ch;

}

return res;

}

40 views

0 replies

0 upvotes

Interview problems

Easy C++ solution

```
#include <bits/stdc++.h>
int ninjaParentheses(string str, int n) {
int ans=0;
stack<pair<int,int>>stk;
// first -- index;
// second -- score;
for(int i=0;i<str.length();i++) {
if(str[i]=='(') {
stk.push({i,0});
}
else {
auto node=stk.top();
stk.pop();
if(node.first==i-1) {
if(stk.empty()) {
ans++;
}
else {
stk.top().second++;
}
}
else {
int score=node.second*2;
if(stk.empty()) {
ans+=score;
}
else {
stk.top().second+=score;
}
}
}
}
return ans;
}
```

146 views

0 replies

0 upvotes

Interview problems

Discussion thread on Interview Problem | Score of Parentheses

Hey everyone, creating this thread to discuss the interview problem - Score of Parentheses.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Score of Parentheses

103 views

2 replies

0 upvotes