Question

Given a parentheses string s, compute the score of the string based on the following rule: • If s is not balanced, the score is 0. • () has score 1. • AB has score A + B, where A and B are balanced parentheses strings. • (A) has score 2 * A, where A is a balanced parentheses string. A balanced string satisfies the following requirements: • The number of ‘(’ equals the number of ‘)’ in the string. • Counting from the first position to any position in the string, the number of ‘(’ is greater than or equal to the number of ‘)’ in the string. (For example, ‘)(’ is not balanced.) The length of s is at most 30. Input: The input is a parentheses string s. Output: Print the score of s. Examples:

1. Input: (())

Output: 2

2. Input: (()(()))

Output: 6

3. Input: ((()())

Output: 0

sketch code:

#include <iostream>

#include <string>

using namespace std;

void SolveC(){

string s;

cin >> s;

/* your code starts here */

}

int main() {

SolveC();

return 0;

}

Answer 1

The solution to the above problem in c++11 is as follows:-

Code-

#include <iostream>
#include <string>
#include <stack>
using namespace std;

void SolveC(){
   string s;
   cin >> s;
   /* your code starts here */
   int finalscore = 0; //calculate final score
   stack <int> st;//Stack to store scores
   for(int i = 0; i < s.length(); i++){
      
       if(s[i] == '('){
           st.push(-1); //Push -1 into the stack for just open parenthesis
       }else{
           if(st.top() == -1){
               st.pop();
               st.push(1); //push score of single () into the stack
           }else{
               int score=0;
               //Calculate score of substring
               while(st.top()!=-1){
                   score+=st.top();
                   st.pop();
                   if(st.empty()){ //Print 0 in case of unbalanced paranthesis
                       cout<<"0\n";
                       return;
                   }
               }
               score=2*score;              
               st.pop();
               st.push(score);
           }
       }
   }
   //Calculate final scores
   while(!st.empty()){
       if(st.top()==-1){ //Print 0 in case of unbalanced paranthesis
           cout<<"0\n";
           return;
       }
       finalscore += st.top();
       st.pop();
   }
   cout<<finalscore<<"\n";
}

int main() {
SolveC();
return 0;
}

Code Screenshots-

Outputs-

Feel free to comment for any issues, do rate the answer positively