Score of Parentheses in C++

Suppose we have a balanced parentheses string S, we have to compute the score of the string based on the following rule −

• The () has score 1
• AB has score A + B, where A and B are two balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

So if the input is like “(()(()))”, then the output will be 6.

To solve this, we will follow these steps −

• ans := 0, define a stack st
• for i in range 0 to size of string S
  • if S[i] is opening parentheses, then insert -1 into stack
  • otherwise
    • if top of stack is -1, then delete from stack and insert 1 into stack
    • otherwise
      • x := 0
      • while top of stack is not -1
        • increase x by st, delete from st
      • x := x * 2
      • delete from st, and insert x
• while stack is not empty
  • increase ans by top of st, and delete top element
• return ans.

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    int scoreOfParentheses(string S) {       int ans = 0;       stack <int> st;       for(int i = 0; i < S.size(); i+=1){          if(S[i] == '('){             st.push(-1);          }else{             if(st.top() == -1){                st.pop();                st.push(1);             }else{                int x = 0;                while(st.top() != -1){                   x += st.top();                   st.pop();                }                x *= 2;                st.pop();                st.push(x);             }          }       }       while(!st.empty()){          ans += st.top();          st.pop();       }       return ans;    } }; main(){    Solution ob;    cout << (ob.scoreOfParentheses("(()(()))")); }

Input

"(()(()))"

Output

6