Score of parentheses using stack

The problem is to calculate the score of a given string of parentheses using a stack. The score of a balanced parentheses string can be determined based on the following rules:

1. A single pair of parentheses "()" contributes a score of 1.
2. For any two balanced parentheses strings A and B, their concatenation AB contributes a score of A + B + A.

The task is to calculate the total score of the given string according to the above rules.

Problem Statement

Given a string containing only the characters '(' and ')', calculate the score of the string based on the above rules and print the result.

Example

Consider the following examples:

1. Input: "(((()))()())" Output: Score = 12 Explanation: The string can be divided into the following groups of balanced parentheses: ((())) = 4 () = 1 () = 1 The total score is 2 * (4 + 1 + 1) = 12.

2. Input: "()()()" Output: Score = 3 Explanation: The string can be divided into three pairs of balanced parentheses, and each pair contributes a score of 1. The total score is 1 + 1 + 1 = 3.

Idea to Solve the Problem

To calculate the score of the given string, we can use a stack to keep track of the score of each group of balanced parentheses. We initialize an empty stack called entry. We iterate through the string from left to right, and for each character, we do the following:

1. If the character is '(', we push a score of 0 onto the stack. This represents the start of a new group of balanced parentheses.
2. If the character is ')', we calculate the score of the current group of balanced parentheses. We pop the top element from the stack, which represents the score of the current group. We then double this score and add it to the previous score on top of the stack (if any) to account for the concatenation rule. We then push the new score back onto the stack.
3. If the character is neither '(' nor ')', the input string contains invalid characters, and we should return.

After processing all characters, the final score will be at the top of the stack, and we can print it as the result.

Pseudocode

Function scoreOfParentheses(text):
    Create an empty stack entry
    Push 0 onto entry

    for each character ch in text:
        if ch is '(':
            Push 0 onto entry
        else if ch is ')':
            Pop score from the top of entry and store it in auxiliary
            Multiply auxiliary by 2
            If auxiliary is 0, set auxiliary to 1
            If entry is empty:
                Return (given parentheses are valid but not balanced)
            Else:
                Pop another score from the top of entry and add it to auxiliary
            Push auxiliary onto entry
        else:
            Return (invalid parentheses)

    Score is the top element of entry
    Print "Score: " + Score

Algorithm

1. Create a class called Score.
2. Define a function called scoreOfParentheses that takes a string text as a parameter.
3. Create an empty stack called entry.
4. Push 0 onto the stack entry to represent the start of a new group of balanced parentheses.
5. Iterate through each character ch in the input string text.
6. For each character, do the following: a. If the character is '(', push 0 onto the stack entry to represent the start of a new group of balanced parentheses. b. If the character is ')', do the following: i. Pop the top element from the stack entry and store it in the variable auxiliary. ii. Double the value of auxiliary. iii. If auxiliary is 0, set it to 1 to account for single pair of parentheses. iv. If the stack entry is empty, return as the given parentheses are valid but not balanced. v. Otherwise, pop another score from the top of the stack entry and add it to auxiliary to account for concatenation rule. vi. Push the new value of auxiliary onto the stack entry. c. If the character is neither '(' nor ')', return as the input contains invalid characters.
7. After processing all characters, the final score will be at the top of the stack entry, print it as the result.

Code Solution

• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

import java.util.Stack;
/*
    Java program for
    Score of parentheses using stack
*/
public class Score
{
	public void scoreOfParentheses(String text)
	{
		int score = 0;
		int n = text.length();
		if (n > 0)
		{
			Stack < Integer > entry = new Stack < Integer > ();
			// First entry
			entry.push(0);
			int auxiliary = 0;
			for (int i = 0; i < n; ++i)
			{
				if (text.charAt(i) == '(')
				{
					entry.push(0);
				}
				else if (text.charAt(i) == ')' && !entry.isEmpty())
				{
					auxiliary = entry.peek();
					entry.pop();
					auxiliary = auxiliary * 2;
					if (auxiliary == 0)
					{
						auxiliary = 1;
					}
					if (entry.isEmpty())
					{
                      	// Assume that given parentheses are valid 
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						auxiliary += entry.peek();
						entry.pop();
					}
					// Add new score
					entry.push(auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
			}
			score = entry.peek();
		}
		System.out.println(" Given Parentheses : " + text);
		System.out.println(" Score : " + score);
	}
	public static void main(String[] args)
	{
		Score task = new Score();
		/*
		    Parentheses :  (((()))()())
		            
		    (((()))()())
		     
		    Here :
		        ((())) = 4   
		            () = 1
		            () = 1
		    ----------------------------------        
		    2 * ( 4 + 1 + 1)     = 12
		   ------------------------------------

		*/
		task.scoreOfParentheses("(((()))()())");
		/*
		    Parentheses :  ()()()
		                    - - -
		                   1+1+1  = 3
		*/
		task.scoreOfParentheses("()()()");
	}
}

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
/*
    C++ program for
    Score of parentheses using stack
*/
class Score
{
	public: void scoreOfParentheses(string text)
	{
		int score = 0;
		int n = text.length();
		if (n > 0)
		{
			stack < int > entry;
			// First entry
			entry.push(0);
			int auxiliary = 0;
			for (int i = 0; i < n; ++i)
			{
				if (text[i] == '(')
				{
					entry.push(0);
				}
				else if (text[i] == ')' && !entry.empty())
				{
					auxiliary = entry.top();
					entry.pop();
					auxiliary = auxiliary *2;
					if (auxiliary == 0)
					{
						auxiliary = 1;
					}
					if (entry.empty())
					{
						// Assume that given parentheses are valid
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						auxiliary += entry.top();
						entry.pop();
					}
					// Add new score
					entry.push(auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
			}
			score = entry.top();
		}
		cout << " Given Parentheses : " << text << endl;
		cout << " Score : " << score << endl;
	}
};
int main()
{
	Score *task = new Score();
	/*
	    Parentheses :  (((()))()())
	            
	    (((()))()())
	     
	    Here :
	        ((())) = 4   
	            () = 1
	            () = 1
	    ----------------------------------        
	    2 *( 4 + 1 + 1)     = 12
	   ------------------------------------
	*/
	task->scoreOfParentheses("(((()))()())");
	/*
	    Parentheses :  ()()()
	                    - - -
	                   1+1+1  = 3
	*/
	task->scoreOfParentheses("()()()");
	return 0;
}

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Score of parentheses using stack
*/
public class Score
{
	public void scoreOfParentheses(String text)
	{
		int score = 0;
		int n = text.Length;
		if (n > 0)
		{
			Stack < int > entry = new Stack < int > ();
			// First entry
			entry.Push(0);
			int auxiliary = 0;
			for (int i = 0; i < n; ++i)
			{
				if (text[i] == '(')
				{
					entry.Push(0);
				}
				else if (text[i] == ')' && !(entry.Count == 0))
				{
					auxiliary = entry.Peek();
					entry.Pop();
					auxiliary = auxiliary * 2;
					if (auxiliary == 0)
					{
						auxiliary = 1;
					}
					if ((entry.Count == 0))
					{
						// Assume that given parentheses are valid
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						auxiliary += entry.Peek();
						entry.Pop();
					}
					// Add new score
					entry.Push(auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
			}
			score = entry.Peek();
		}
		Console.WriteLine(" Given Parentheses : " + text);
		Console.WriteLine(" Score : " + score);
	}
	public static void Main(String[] args)
	{
		Score task = new Score();
		/*
		    Parentheses :  (((()))()())
		            
		    (((()))()())
		     
		    Here :
		        ((())) = 4   
		            () = 1
		            () = 1
		    ----------------------------------        
		    2 * ( 4 + 1 + 1)     = 12
		   ------------------------------------
		*/
		task.scoreOfParentheses("(((()))()())");
		/*
		    Parentheses :  ()()()
		                    - - -
		                   1+1+1  = 3
		*/
		task.scoreOfParentheses("()()()");
	}
}

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

package main

import "fmt"
/*
    Go program for
    Score of parentheses using stack
*/

func scoreOfParentheses(text string) {
	var score int = 0
	var n int = len(text)
	if n > 0 {
		var entry = make([] int, 0)
		// First entry
		entry = append(entry, 0)
		var auxiliary int = 0
		for i := 0 ; i < n ; i++ {
			if text[i] == '(' {
				entry = append(entry, 0)
			} else if text[i] == ')' && len(entry) != 0 {
				auxiliary = entry[len(entry) - 1]
				entry = entry[: len(entry) - 1]
				auxiliary = auxiliary * 2
				if auxiliary == 0 {
					auxiliary = 1
				}
				if len(entry) == 0 {
					// Assume that given parentheses are valid
					// But Parentheses are not balanced
					return
				} else {
					// Get current top scorer
					auxiliary += entry[len(entry) - 1]
					entry = entry[: len(entry) - 1]
				}
				// Add new score
				entry = append(entry, auxiliary)
			} else {
				// Invalid parentheses
				return
			}
		}
		score = entry[len(entry) - 1]
	}
	fmt.Println(" Given Parentheses : ", text)
	fmt.Println(" Score : ", score)
}
func main() {

	/*
	    Parentheses :  (((()))()())
	            
	    (((()))()())
	     
	    Here :
	        ((())) = 4   
	            () = 1
	            () = 1
	    ----------------------------------        
	    2 * ( 4 + 1 + 1)     = 12
	   ------------------------------------
	*/
	scoreOfParentheses("(((()))()())")
	/*
	    Parentheses :  ()()()
	                    - - -
	                   1+1+1  = 3
	*/
	scoreOfParentheses("()()()")
}

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

<?php
/*
    Php program for
    Score of parentheses using stack
*/
class Score
{
	public	function scoreOfParentheses($text)
	{
		$score = 0;
		$n = strlen($text);
		if ($n > 0)
		{
			$entry = array();
			// First entry
			array_push($entry, 0);
			$auxiliary = 0;
			for ($i = 0; $i < $n; ++$i)
			{
				if ($text[$i] == '(')
				{
					array_push($entry, 0);
				}
				else if ($text[$i] == ')' && !empty($entry))
				{
					$auxiliary = end($entry);
					array_pop($entry);
					$auxiliary = $auxiliary * 2;
					if ($auxiliary == 0)
					{
						$auxiliary = 1;
					}
					if (empty($entry))
					{
						// Assume that given parentheses are valid
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						$auxiliary += end($entry);
						array_pop($entry);
					}
					// Add new score
					array_push($entry, $auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
			}
			$score = end($entry);
		}
		echo(" Given Parentheses : ".$text.
			"\n");
		echo(" Score : ".$score.
			"\n");
	}
}

function main()
{
	$task = new Score();
	/*
	    Parentheses :  (((()))()())
	            
	    (((()))()())
	     
	    Here :
	        ((())) = 4   
	            () = 1
	            () = 1
	    ----------------------------------        
	    2 * ( 4 + 1 + 1)     = 12
	   ------------------------------------
	*/
	$task->scoreOfParentheses("(((()))()())");
	/*
	    Parentheses :  ()()()
	                    - - -
	                   1+1+1  = 3
	*/
	$task->scoreOfParentheses("()()()");
}
main();

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

/*
    Node JS program for
    Score of parentheses using stack
*/
class Score
{
	scoreOfParentheses(text)
	{
		var score = 0;
		var n = text.length;
		if (n > 0)
		{
			var entry = [];
			// First entry
			entry.push(0);
			var auxiliary = 0;
			for (var i = 0; i < n; ++i)
			{
				if (text.charAt(i) == '(')
				{
					entry.push(0);
				}
				else if (text.charAt(i) == ')' && !(entry.length == 0))
				{
					auxiliary = entry[entry.length - 1];
					entry.pop();
					auxiliary = auxiliary * 2;
					if (auxiliary == 0)
					{
						auxiliary = 1;
					}
					if ((entry.length == 0))
					{
						// Assume that given parentheses are valid
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						auxiliary += entry[entry.length - 1];
						entry.pop();
					}
					// Add new score
					entry.push(auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
			}
			score = entry[entry.length - 1];
		}
		console.log(" Given Parentheses : " + text);
		console.log(" Score : " + score);
	}
}

function main()
{
	var task = new Score();
	/*
	    Parentheses :  (((()))()())
	            
	    (((()))()())
	     
	    Here :
	        ((())) = 4   
	            () = 1
	            () = 1
	    ----------------------------------        
	    2 * ( 4 + 1 + 1)     = 12
	   ------------------------------------
	*/
	task.scoreOfParentheses("(((()))()())");
	/*
	    Parentheses :  ()()()
	                    - - -
	                   1+1+1  = 3
	*/
	task.scoreOfParentheses("()()()");
}
main();

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

#    Python 3 program for
#    Score of parentheses using stack
class Score :
	def scoreOfParentheses(self, text) :
		score = 0
		n = len(text)
		if (n > 0) :
			entry = []
			#  First entry
			entry.append(0)
			auxiliary = 0
			i = 0
			while (i < n) :
				if (text[i] == '(') :
					entry.append(0)
				elif (text[i] == ')'
					and not(len(entry) == 0)) :
					auxiliary = entry[-1]
					entry.pop()
					auxiliary = auxiliary * 2
					if (auxiliary == 0) :
						auxiliary = 1
					
					if ((len(entry) == 0)) :
						#  Assume that given parentheses are valid
						#  But Parentheses are not balanced
						return
					else :
						#  Get current top scorer
						auxiliary += entry[-1]
						entry.pop()
					
					#  Add new score
					entry.append(auxiliary)
				else :
					#  Invalid parentheses
					return
				
				i += 1
			
			score = entry[-1]
		
		print(" Given Parentheses : ", text)
		print(" Score : ", score)
	

def main() :
	task = Score()
	#    Parentheses :  (((()))()())
	#    (((()))()())
	#    Here :
	#        ((())) = 4   
	#            () = 1
	#            () = 1
	#    ----------------------------------        
	#    2 * ( 4 + 1 + 1)     = 12
	#   ------------------------------------
	task.scoreOfParentheses("(((()))()())")
	#    Parentheses :  ()()()
	#                    - - -
	#                   1+1+1  = 3
	task.scoreOfParentheses("()()()")

if __name__ == "__main__": main()

 Given Parentheses :  (((()))()())
 Score :  12
 Given Parentheses :  ()()()
 Score :  3

#    Ruby program for
#    Score of parentheses using stack
class Score 
	def scoreOfParentheses(text) 
		score = 0
		n = text.length
		if (n > 0) 
			entry = []
			#  First entry
			entry.push(0)
			auxiliary = 0
			i = 0
			while (i < n) 
				if (text[i] == '(') 
					entry.push(0)
				elsif (text[i] == ')' && !(entry.length == 0)) 
					auxiliary = entry.last
					entry.pop()
					auxiliary = auxiliary * 2
					if (auxiliary == 0) 
						auxiliary = 1
					end

					if ((entry.length == 0)) 
						#  Assume that given parentheses are valid
						#  But Parentheses are not balanced
						return
					else
 
						#  Get current top scorer
						auxiliary += entry.last
						entry.pop()
					end

					#  Add new score
					entry.push(auxiliary)
				else
 
					#  Invalid parentheses
					return
				end

				i += 1
			end

			score = entry.last
		end

		print(" Given Parentheses : ", text, "\n")
		print(" Score : ", score, "\n")
	end

end

def main() 
	task = Score.new()
	#    Parentheses :  (((()))()())
	#    (((()))()())
	#    Here :
	#        ((())) = 4   
	#            () = 1
	#            () = 1
	#    ----------------------------------        
	#    2 * ( 4 + 1 + 1)     = 12
	#   ------------------------------------
	task.scoreOfParentheses("(((()))()())")
	#    Parentheses :  ()()()
	#                    - - -
	#                   1+1+1  = 3
	task.scoreOfParentheses("()()()")
end

main()

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

import scala.collection.mutable._;
/*
    Scala program for
    Score of parentheses using stack
*/
class Score()
{
	def scoreOfParentheses(text: String): Unit = {
		var score: Int = 0;
		var n: Int = text.length();
		if (n > 0)
		{
			var entry: Stack[Int] = new Stack[Int]();
			// First entry
			entry.push(0);
			var auxiliary: Int = 0;
			var i: Int = 0;
			while (i < n)
			{
				if (text.charAt(i) == '(')
				{
					entry.push(0);
				}
				else if (text.charAt(i) == ')' && !entry.isEmpty)
				{
					auxiliary = entry.top;
					entry.pop;
					auxiliary = auxiliary * 2;
					if (auxiliary == 0)
					{
						auxiliary = 1;
					}
					if (entry.isEmpty)
					{
						// Assume that given parentheses are valid
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						auxiliary += entry.top;
						entry.pop;
					}
					// Add new score
					entry.push(auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
				i += 1;
			}
			score = entry.top;
		}
		println(" Given Parentheses : " + text);
		println(" Score : " + score);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Score = new Score();
		/*
		    Parentheses :  (((()))()())
		            
		    (((()))()())
		     
		    Here :
		        ((())) = 4   
		            () = 1
		            () = 1
		    ----------------------------------        
		    2 * ( 4 + 1 + 1)     = 12
		   ------------------------------------
		*/
		task.scoreOfParentheses("(((()))()())");
		/*
		    Parentheses :  ()()()
		                    - - -
		                   1+1+1  = 3
		*/
		task.scoreOfParentheses("()()()");
	}
}

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

import Foundation;
/*
    Swift 4 program for
    Score of parentheses using stack
*/
struct Stack
{
	private
	var items: [Int] = []
	func peek()->Int
	{
		if (self.isEmpty()==false)
		{
			return items.first!
		}
		else
		{
			fatalError("This stack is empty.")
		}
	}
	func isEmpty()->Bool
	{
		return items.count == 0
	}
	mutating func pop()
	{
		items.removeFirst()
	}
	mutating func push(_ data: Int)
	{
		items.insert(data, at: 0)
	}
}
class Score
{
	func scoreOfParentheses(_ data: String)
	{
      	let text = Array(data);
		var score: Int = 0;
		let n: Int = text.count;
		if (n > 0)
		{
			var entry = Stack();
			// First entry
			entry.push(0);
			var auxiliary: Int = 0;
			var i: Int = 0;
			while (i < n)
			{
				if (text[i] == "(")
				{
					entry.push(0);
				}
				else if (text[i] == ")" && !entry.isEmpty())
				{
					auxiliary = entry.peek();
					entry.pop();
					auxiliary = auxiliary * 2;
					if (auxiliary == 0)
					{
						auxiliary = 1;
					}
					if (entry.isEmpty())
					{
						// Assume that given parentheses are valid
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						auxiliary += entry.peek();
						entry.pop();
					}
					// Add new score
					entry.push(auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
				i += 1;
			}
			score = entry.peek();
		}
		print(" Given Parentheses : ", data);
		print(" Score : ", score);
	}
}
func main()
{
	let task: Score = Score();
	/*
	    Parentheses :  (((()))()())
	            
	    (((()))()())
	     
	    Here :
	        ((())) = 4   
	            () = 1
	            () = 1
	    ----------------------------------        
	    2 * ( 4 + 1 + 1)     = 12
	   ------------------------------------
	*/
	task.scoreOfParentheses("(((()))()())");
	/*
	    Parentheses :  ()()()
	                    - - -
	                   1+1+1  = 3
	*/
	task.scoreOfParentheses("()()()");
}
main();

 Given Parentheses :  (((()))()())
 Score :  12
 Given Parentheses :  ()()()
 Score :  3

import java.util.Stack;
/*
    Kotlin program for
    Score of parentheses using stack
*/
class Score
{
	fun scoreOfParentheses(text: String): Unit
	{
		var score: Int = 0;
		val n: Int = text.length;
		if (n > 0)
		{
			val entry: Stack < Int > = Stack < Int > ();
			// First entry
			entry.push(0);
			var auxiliary: Int ;
			var i: Int = 0;
			while (i < n)
			{
				if (text.get(i) == '(')
				{
					entry.push(0);
				}
				else if (text.get(i) == ')' && !entry.empty())
				{
					auxiliary = entry.peek();
					entry.pop();
					auxiliary = auxiliary * 2;
					if (auxiliary == 0)
					{
						auxiliary = 1;
					}
					if (entry.empty())
					{
						// Assume that given parentheses are valid
						// But Parentheses are not balanced
						return;
					}
					else
					{
						// Get current top scorer
						auxiliary += entry.peek();
						entry.pop();
					}
					// Add new score
					entry.push(auxiliary);
				}
				else
				{
					// Invalid parentheses
					return;
				}
				i += 1;
			}
			score = entry.peek();
		}
		println(" Given Parentheses : " + text);
		println(" Score : " + score);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Score = Score();
	/*
	    Parentheses :  (((()))()())
	            
	    (((()))()())
	     
	    Here :
	        ((())) = 4   
	            () = 1
	            () = 1
	    ----------------------------------        
	    2 * ( 4 + 1 + 1)     = 12
	   ------------------------------------
	*/
	task.scoreOfParentheses("(((()))()())");
	/*
	    Parentheses :  ()()()
	                    - - -
	                   1+1+1  = 3
	*/
	task.scoreOfParentheses("()()()");
}

 Given Parentheses : (((()))()())
 Score : 12
 Given Parentheses : ()()()
 Score : 3

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of characters in the input string text. This is because we perform a single pass through the input string and each character is processed once. The use of the stack does not significantly affect the overall time complexity.