Posted on by Kalkicode
Code Stack

# 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

``````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();
}
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)
{
/*
Parentheses :  (((()))()())

(((()))()())

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------

*/
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
}
}``````

#### Output

`````` 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();
}
entry.push(auxiliary);
}
else
{
// Invalid parentheses
return;
}
}
score = entry.top();
}
cout << " Given Parentheses : " << text << endl;
cout << " Score : " << score << endl;
}
};
int main()
{
/*
Parentheses :  (((()))()())

(((()))()())

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 *( 4 + 1 + 1)     = 12
------------------------------------
*/
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
return 0;
}``````

#### Output

`````` 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();
}
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)
{
/*
Parentheses :  (((()))()())

(((()))()())

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

#### Output

`````` 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]
}
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("()()()")
}``````

#### Output

`````` 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);
}
array_push(\$entry, \$auxiliary);
}
else
{
// Invalid parentheses
return;
}
}
\$score = end(\$entry);
}
echo(" Given Parentheses : ".\$text.
"\n");
echo(" Score : ".\$score.
"\n");
}
}

function main()
{
/*
Parentheses :  (((()))()())

(((()))()())

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
}
main();``````

#### Output

`````` 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();
}
entry.push(auxiliary);
}
else
{
// Invalid parentheses
return;
}
}
score = entry[entry.length - 1];
}
console.log(" Given Parentheses : " + text);
console.log(" Score : " + score);
}
}

function main()
{
/*
Parentheses :  (((()))()())

(((()))()())

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
}
main();``````

#### Output

`````` 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()

entry.append(auxiliary)
else :
#  Invalid parentheses
return

i += 1

score = entry[-1]

print(" Given Parentheses : ", text)
print(" Score : ", score)

def main() :
#    Parentheses :  (((()))()())
#    (((()))()())
#    Here :
#        ((())) = 4
#            () = 1
#            () = 1
#    ----------------------------------
#    2 * ( 4 + 1 + 1)     = 12
#   ------------------------------------
#    Parentheses :  ()()()
#                    - - -
#                   1+1+1  = 3

if __name__ == "__main__": main()``````

#### Output

`````` 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

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()
#    Parentheses :  (((()))()())
#    (((()))()())
#    Here :
#        ((())) = 4
#            () = 1
#            () = 1
#    ----------------------------------
#    2 * ( 4 + 1 + 1)     = 12
#   ------------------------------------
#    Parentheses :  ()()()
#                    - - -
#                   1+1+1  = 3
end

main()``````

#### Output

`````` 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;
}
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
------------------------------------
*/
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
}
}``````

#### Output

`````` 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();
}
entry.push(auxiliary);
}
else
{
// Invalid parentheses
return;
}
i += 1;
}
score = entry.peek();
}
print(" Given Parentheses : ", data);
print(" Score : ", score);
}
}
func main()
{
/*
Parentheses :  (((()))()())

(((()))()())

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
}
main();``````

#### Output

`````` 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();
}
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
{
/*
Parentheses :  (((()))()())

(((()))()())

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

#### Output

`````` 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.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post