Score of Parentheses

Problem Statement:

You are given a string consisting of pair of balanced parentheses. You need to calculate the total score of the given string as below:

“()” has a score of 1.
“m n” has a score of m + n where m and n are individual pairs of balanced parentheses.
“(m)” has a score twice of m (i.e), 2 * score of m.

Example

Input: (()())()

2 * (2) = 4 + 1

= 5

Solution

For this solution we will use stack.

We iterate through all the characters of the string.

If the current character is “(“, then push into the stack.

Else if the current element is “)”, we check the top of the stack. If the top of the stack is “(“, then we insert “1”.

Else double the top element of the stack and then push the value into the stack.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 

using namespace std;


long score_of_parentheses(string S)
{
 
    stack<string> s;
 
    int i = 0;
    
    long ans = 0;

    while (i < S.length()) 
    {
 
        if (S[i] == '(')
            s.push("(");
        else {
 
            if (s.top() == "(") 
            {
                s.pop();
                s.push("1");
            }
            else 
            {
 
                long count = 0;
 
                while (s.top() != "(") 
                {
                    count += stoi(s.top());
                    s.pop();
                }
 
                s.pop();

                s.push(to_string(2 * count));
            }
        }
 
        i++;
    }
 
    while (!s.empty()) 
    {
 
        ans += stoi(s.top());
        s.pop();
    }
    return ans;
}
 
int main()
{
    string S1 = "(()(()))";
    cout << score_of_parentheses(S1) << endl;
 
    return 0;
}

Output:

6