Given a string str consisting of pairs of balanced parentheses, the task is to calculate the score of the given string based on the following rules:
- “()” has a score of 1.
- “x y” has a score of x + y where x and y are individual pairs of balanced parentheses.
- “(x)” has a score twice of x (i.e), 2 * score of x.
Examples:
Input: str = “()()”
Output: 2
Explanation: There are two individual pairs of balanced parentheses “() ()”. Therefore, score = score of “()” + score of “()” = 1 + 1 = 2Input: str = “(())”
Output: 2
Explanation: Since the input is of the form “(x)”, the total score = 2 * score of “()” = 2 * 1 = 2
Approach: The problem can be solved using Stack. The idea is to iterate over the characters of the string. For every ith character check if the character is ‘(‘ or not. If found to be true, then insert the character into the stack. Otherwise, calculate the score of the inner parentheses and insert double of the score into the stack. Follow the steps below to solve the problem:
- Initialize a stack to store the current traversed character or the score of inner balanced parentheses.
- Iterate over the characters of the string, str. For every ith character check the following conditions:
- If the current character is ‘(‘ or not. If found to be true, then push the current character into the stack.
- Otherwise, check if the top element of the stack is ‘(‘ or not. If found to be true, then insert “1” into the stack which represents the score of the inner balanced parentheses.
- Otherwise, double the top element of the stack and push the obtained value into the stack.
- Finally, print the total score obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <iostream>#include <stack>using namespace std;// Function to calculate// score of parentheseslong long scoreOfParentheses(string S){ stack<string> s; // Stores index of // character of string int i = 0; // Stores total scores // obtained from the string long long ans = 0; // Iterate over characters // of the string while (i < S.length()) { // If s[i] is '(' if (S[i] == '(') s.push("("); else { // If top element of // stack is '(' if (s.top() == "(") { s.pop(); s.push("1"); } else { // Stores score of // inner parentheses long long count = 0; // Calculate score of // inner parentheses while (s.top() != "(") { // Update count count += stoi(s.top()); s.pop(); } // Pop from stack s.pop(); // Insert score of // inner parentheses s.push(to_string(2 * count)); } } // Update i i++; } // Calculate score // of the string while (!s.empty()) { // Update ans ans += stoi(s.top()); s.pop(); } return ans;}// Driver Codeint main(){ string S1 = "(()(()))"; cout << scoreOfParentheses(S1) << endl; return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to calculate // score of parentheses static long scoreOfParentheses(String S) { Stack<String> s = new Stack<>(); // Stores index of // character of String int i = 0; // Stores total scores // obtained from the String long ans = 0; // Iterate over characters // of the String while (i < S.length()) { // If s[i] is '(' if (S.charAt(i) == '(') s.add("("); else { // If top element of // stack is '(' if (s.peek() == "(") { s.pop(); s.add("1"); } else { // Stores score of // inner parentheses long count = 0; // Calculate score of // inner parentheses while (s.peek() != "(") { // Update count count += Integer.parseInt(s.peek()); s.pop(); } // Pop from stack s.pop(); // Insert score of // inner parentheses s.add(String.valueOf(2 * count)); } } // Update i i++; } // Calculate score // of the String while (!s.isEmpty()) { // Update ans ans += Integer.parseInt(s.peek()); s.pop(); } return ans; } // Driver Code public static void main(String[] args) { String S1 = "(()(()))"; System.out.print(scoreOfParentheses(S1) +"\n"); }}// This code is contributed by 29AjayKumar. |
Python3
# Python3 program to implement# the above approach# Function to calculate# score of parenthesesdef scoreOfParentheses(S): s = [] # Stores index of # character of string i = 0 # Stores total scores # obtained from the string ans = 0 # Iterate over characters # of the string while (i < len(S)): # If s[i] is '(' if (S[i] == '('): s.append("(") else: # If top element of # stack is '(' if (s[-1] == "("): s.pop() s.append("1") else: # Stores score of # inner parentheses count = 0 # Calculate score of # inner parentheses while (s[-1] != "("): # Update count count += int(s[-1]) s.pop() # Pop from stack s.pop() # Insert score of # inner parentheses s.append(str(2 * count)) # Update i i += 1 # Calculate score # of the string while len(s) > 0: # Update ans ans += int(s[-1]) s.pop() return ans # Driver Codeif __name__ == '__main__': S1 = "(()(()))" print(scoreOfParentheses(S1)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ // Function to calculate // score of parentheses static long scoreOfParentheses(String S) { Stack<String> s = new Stack<String>(); // Stores index of // character of String int i = 0; // Stores total scores // obtained from the String long ans = 0; // Iterate over characters // of the String while (i < S.Length) { // If s[i] is '(' if (S[i] == '(') s.Push("("); else { // If top element of // stack is '(' if (s.Peek() == "(") { s.Pop(); s.Push("1"); } else { // Stores score of // inner parentheses long count = 0; // Calculate score of // inner parentheses while (s.Peek() != "(") { // Update count count += Int32.Parse(s.Peek()); s.Pop(); } // Pop from stack s.Pop(); // Insert score of // inner parentheses s.Push(String.Join("", 2 * count)); } } // Update i i++; } // Calculate score // of the String while (s.Count != 0) { // Update ans ans += Int32.Parse(s.Peek()); s.Pop(); } return ans; } // Driver Code public static void Main(String[] args) { String S1 = "(()(()))"; Console.Write(scoreOfParentheses(S1) +"\n"); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to implement// the above approach// Function to calculate// score of parenthesesfunction scoreOfParentheses(S){ var s = []; // Stores index of // character of string var i = 0; // Stores total scores // obtained from the string var ans = 0; // Iterate over characters // of the string while (i < S.length) { // If s[i] is '(' if (S[i] == '(') s.push("("); else { // If top element of // stack is '(' if (s[s.length-1] == "(") { s.pop(); s.push("1"); } else { // Stores score of // inner parentheses var count = 0; // Calculate score of // inner parentheses while (s[s.length-1] != "(") { // Update count count += parseInt(s[s.length-1]); s.pop(); } // Pop from stack s.pop(); // Insert score of // inner parentheses s.push((2 * count).toString()); } } // Update i i++; } // Calculate score // of the string while (s.length!=0) { // Update ans ans += parseInt(s[s.length-1]); s.pop(); } return ans;}// Driver Codevar S1 = "(()(()))";document.write( scoreOfParentheses(S1));</script> |
Output:
6
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
