Score of Balanced Parentheses

Given a string s, consisting of pairs of balanced parentheses, find the score of the given string based on the given rules:

• “()” has a score of 1.
• “A B” has a score of A + B, where A and B are individual pairs of balanced parentheses.
• “(A)” has a score twice of A i.e., the score is 2 * score of A.

Examples:

Input: s = “()()” 
Output: 2 
Explanation: The string s is of the form "AB", that makes the total score = (score of A) + (score of B) = 1 + 1 = 2.

Input: s = "(()(()))"
Output: 6
Explanation: The string s is of the form "(A(B))" which makes the total score = 2 × ((score of A) + 2 × (score of B)) = 2 × (1 + 2 × (1)) = 6.

[Approach] Using Stack - O(n) Time and O(n) Space

Think of the string as a tree-like structure:

• Every '(' means we are going down to a child level.
• Every ')' means we are returning back to the parent level.

To keep track of scores at each level, we use a stack.

Now, how does the stack help?

The stack keeps track of the score at each level. When we go down '(', we push 0 to start for that level. When we come back through ')', we pop the score of that level:

• If it was empty "()", score = 1.
• If it had children "(A)", score = 2 × innerScore.

Then we add this score to the parent’s score (the new top of the stack). At the end, only the root score is left in the stack and that’s our total score.

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

int scoreOfParentheses(string &s) {
    stack<int> st;
    st.push(0);

    for (char c : s) {
        
        // start a new score scope
        if (c == '(') {
            st.push(0);
        } else {
            int tmp = st.top();
            st.pop();

            int val;
            
            // calculate score for current level
            if (tmp > 0)
                val = 2 * tmp;
            else
                val = 1;

            // add current level score to parent
            st.top() += val;
        }
    }

    return st.top();
}

int main()
{
    string s = "(()(()))";
    cout << scoreOfParentheses(s);
    return 0;
}

import java.util.Stack;

class GFG {
    public static int scoreOfParentheses(String s) {
        
        Stack<Integer> st = new Stack<>();
        st.push(0);

        for (char c : s.toCharArray()) {
          
            // start a new score scope
            if (c == '(') {
                st.push(0);
            } else {
                int tmp = st.pop();

                // calculate score for current level
                int val = (tmp > 0) ? 2 * tmp : 1;

                // add current level score to parent
                st.push(st.pop() + val);
            }
        }
        return st.pop();
    }

    public static void main(String[] args) {
        String s = "(()(()))";
        System.out.println(scoreOfParentheses(s));
    }
}

def scoreOfParentheses(s):
    stack = [0]

    for c in s:
        
        # start with new score scope
        if c == '(':
            stack.append(0)
        else:
            tmp = stack.pop()
            
            #  calculate score for current level
            val = 2 * tmp if tmp > 0 else 1
            
            #  add current level score to parent
            stack[-1] += val

    return stack[-1]


if __name__ == '__main__':
    s = "(()(()))"
    print(scoreOfParentheses(s))

using System;
using System.Collections.Generic;

class GFG {
    public static int scoreOfParentheses(string s) {
        Stack<int> st = new Stack<int>();
        st.Push(0); 

        foreach (char c in s) {
            if (c == '(') {
                
                // start a new scope
                st.Push(0);
            } else {
                
                // end of current scope
                int tmp = st.Pop();
                int val = tmp == 0 ? 1 : 2 * tmp;
                
                // add current score to parent scope
                st.Push(st.Pop() + val);
            }
        }

        return st.Pop();
    }

    public static void Main() {
        string s = "(()(()))";
        Console.WriteLine(scoreOfParentheses(s)); 
    }
}

function scoreOfParentheses(s) {
    let st = [0]; 

    for (let c of s) {
        if (c === '(') {
            
            // start a new scope
            st.push(0);
        } else {
            // end of current scope
            let tmp = st.pop();
            let val = tmp === 0 ? 1 : 2 * tmp;
            
            // add current score to parent scope
            st[st.length - 1] += val;
        }
    }

    return st[0];
}

// Driver Code
let s = "(()(()))";
console.log(scoreOfParentheses(s));

6