Problem Statement : https://leetcode.com/problems/score-of-parentheses/

Note: Go check down to view similar kind of problem and approach.

Approach:

• An ideal approach to this kind of problem is to check positions of the closed parentheses ).
• Here, we uses a stack stack = st that pushes the ( and pops whenever a ) appears.
• Check the postions of the closed parentheses and update the answer accordingly.

If you are not interested in the algorithm, please jump to the code.

Algorithm:

1. As discussed above, declare a stack of type int stack<int>. Let ( = -1 in the code (i.e.,) we push -1 in the stack inplace of (.
2. Note, All the substrings () have value 1 by default.
3. Itereate over the string. Whenever we encounter a (, we push -1 in to the stack. Whenever we encounter a ), There can be two cases.
4. First case is (), it is made 1 by default. Pop the -1 and push 1 in to the stack.
5. Second case is ( value1 ... valuen ), Let curr = 0, Here pop the stack values and add to the curr till you encounter -1 in the stack which represents ). Now multiply the curr value by 2 and push it into the stack.
   Ex: (()), Here () = 1 wihch can bre written as (1) (i.e.,) curr = 1 and so we will push curr*2 = 2 in the stack.

Step wise iteration of algorithm:
Given string s = (()(())), stack<int> is empty.

( ( ) ( ( ) ) )
0 1 2 3 4 5 6 7

Iterate over the string,
At pos 0: Push -1 in to the stack. stack = {-1}.

Stack =  |  -1  |
         +------+

At pos 1: Push -1 in to the stack. stack = {-1, -1}.

Stack =  |  -1  |
         +------+
		 |  -1  |
         +------+

At pos 2: Since it is closed parentheses, the one on the top of the stack is -1, it must be (). So, pop the top value = -1 from the stack and push 1 in to the stack. stack = {-1, 1}.

Stack =  |   1  |
         +------+
		 |  -1  |
         +------+

At pos 3: Push -1 in to the stack. stack = {-1, 1, -1}.

Stack =  |  -1  |
         +------+
		 |   1  |
         +------+
		 |  -1  |
         +------+

At pos 4: Push -1 in to the stack. stack = {-1, 1, -1, -1}.

Stack =  |  -1  |
         +------+
		 |  -1  |
         +------+
		 |   1  |
         +------+
		 |  -1  |
         +------+

At pos 5: Since it is closed parentheses, the one on the top of the stack is -1, it must be (). So, pop the top value = -1 from the stack and push 1 in to the stack. stack = {-1, 1, -1, 1}.

Stack =  |   1  |
         +------+
		 |  -1  |
         +------+
		 |   1  |
         +------+
		 |  -1  |
         +------+

At pos 6: Since it is closed parentheses, the one on the top of the stack is not -1, it must be of type ( value1 ... valuen ). So, pop all the values from the stack and add them to the curr varaible, curr = 1, till -1 is encountered. Now, pop the top value = -1 from the stack and push curr*2 = 1*2 = 2 in to the stack. stack = {-1, 1, 2}.

Stack =  |   2  |
         +------+
		 |   1  |
         +------+
		 |  -1  |
         +------+

At pos 7: Since it is closed parentheses, the one on the top of the stack is not -1, it must be of type ( value1 ... valuen ). So, pop all the values from the stack and add them to the curr varaible, curr = 1 + 2 = 3, till -1 is encountered. Now, pop the top value = -1 from the stack and push curr*2 = 3*2 = 6 in to the stack. stack = {6}.

Stack =  |   6  |
         +------+

So, the answer is (()(())) = 6.

Approach: Using Stack

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st; // ( = -1  
        for(auto x : s) {
            if(x == '(') {
                st.push(-1);
            }else {
                if(st.top() == -1) {
                    st.pop(); st.push(1);
                }else {
                    int curr = 0;
                    while(st.top() != -1) {
                        curr += st.top(); st.pop();
                    }
                    st.pop(); st.push(curr*2);                 
                }                
            }
        }
        return st.top();
    }
};

Till now code work fine, but there are some cases where not every valid string is a substring of main string instead there can be many strings side by side (i.e.,) s = () () (()). In such cases, the top of the stack alone doesn't gives the answer. We need to sum up all the values in the stack to get final answer. This can be done as -

int ans = 0;
while(st.size()) {
	ans += st.top(); st.pop();
}
return ans;

Now the final code looks like -

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> st; // ( = -1  
        for(auto x : s) {
            if(x == '(') {
                st.push(-1);
            }else {
                if(st.top() == -1) {
                    st.pop(); st.push(1);
                }else {
                    int curr = 0;
                    while(st.top() != -1) {
                        curr += st.top(); st.pop();
                    }
                    st.pop(); st.push(curr*2);                 
                }                
            }
        }
		int ans = 0;
        while(st.size()) {
            ans += st.top(); st.pop();
        }
        return ans;
    }
};

Similar Problem:
https://leetcode.com/problems/delete-columns-to-make-sorted/
https://leetcode.com/problems/delete-columns-to-make-sorted-ii/

Upvote if you like.
Thank you.