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:
- A single pair of parentheses "()" contributes a score of 1.
- 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:
-
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.
-
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:
- If the character is '(', we push a score of 0 onto the stack. This represents the start of a new group of balanced parentheses.
- 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.
- 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
- Create a class called
Score
. - Define a function called
scoreOfParentheses
that takes a stringtext
as a parameter. - Create an empty stack called
entry
. - Push 0 onto the stack
entry
to represent the start of a new group of balanced parentheses. - Iterate through each character
ch
in the input stringtext
. - 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 stackentry
and store it in the variableauxiliary
. ii. Double the value ofauxiliary
. iii. Ifauxiliary
is 0, set it to 1 to account for single pair of parentheses. iv. If the stackentry
is empty, return as the given parentheses are valid but not balanced. v. Otherwise, pop another score from the top of the stackentry
and add it toauxiliary
to account for concatenation rule. vi. Push the new value ofauxiliary
onto the stackentry
. c. If the character is neither '(' nor ')', return as the input contains invalid characters. - 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();
}
// 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("()()()");
}
}
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();
}
// 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;
}
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();
}
// 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("()()()");
}
}
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]
}
// 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("()()()")
}
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);
}
// 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();
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();
}
// 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();
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()
# 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()
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
# 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()
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;
}
// 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("()()()");
}
}
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();
}
// 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();
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();
}
// 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("()()()");
}
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.
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.
New Comment