Posted on by Kalkicode
Code Tree

# Score of parentheses using tree

The problem involves calculating a score for a given string of parentheses based on a certain set of rules. Each opening parenthesis '(' must be paired with a closing parenthesis ')', and the score of a valid string of parentheses is determined by a recursive process that resembles a tree structure.

## Problem Statement

Given a string containing only opening and closing parentheses, the goal is to calculate the score of the string using the following rules:

1. An empty string or a pair of empty parentheses has a score of 1.
2. If S is a valid string of parentheses, then "(S)" has a score of 2 * score(S).
3. If A and B are valid strings of parentheses, then AB has a score of score(A) + score(B).

## Example

Let's take the string "(((()))()())" as an example.

• ((())) = 4
• () = 1
• () = 1

Total score = 2 * (4 + 1 + 1) = 12

## Idea to Solve

The given code solves this problem using a tree-like structure. It iterates through the input string and constructs a tree of TreeNode objects based on the parentheses structure. Each opening parenthesis creates a new child node, and each closing parenthesis moves back to the parent node. The score is then calculated recursively based on the constructed tree.

## Algorithm

1. Create a TreeNode class with parent and child references.
2. Create a Score class with root as its instance variable and two main methods: `constructTree` and `getScore`.
3. In `constructTree`, iterate through the input string.
• If a '(' is encountered, create a new TreeNode, link it to the parent, and update the auxiliary node.
• If a ')' is encountered, move back to the parent node.
4. In `getScore`, recursively calculate the score.
• If the current node has no children, return 1.
• Otherwise, iterate through the children, summing up the scores of each subtree.
• If the node has a parent, return 2 * total score, else return the total score.

## Pseudocode

``````TreeNode class:
parent
child[]

Score class:
root

constructTree(text):
auxiliary = root
for character in text:
if character == '(':
Create new node
Set parent of new node
Add new node to auxiliary's children
Update auxiliary
else if character == ')':
Move back to parent

getScore(node):
if node has no children:
return 1
totalScore = 0
for child in node's children:
totalScore += getScore(child)
if node has parent:
return 2 * totalScore
else:

main():
s1 = Score("(((()))()())")
Print s1.getScore(s1.root)

s2 = Score("()()()")
Print s2.getScore(s2.root)``````

## Code Solution

``````import java.util.ArrayList;
/*
Java program for
Score of parentheses using tree
*/
class TreeNode
{
public TreeNode parent;
public ArrayList < TreeNode > child;
public TreeNode()
{
this.parent = null;
this.child = new ArrayList < TreeNode > ();
}
}
public class Score
{
public TreeNode root;
public Score(String text)
{
this.root = new TreeNode();
this.constructTree(text);
}
public void constructTree(String text)
{
TreeNode auxiliary = this.root;
for (int i = 0; i < text.length(); ++i)
{
if (auxiliary == null)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (text.charAt(i) == '(')
{
// Create new node of tree
TreeNode node = new TreeNode();
// Set parent
node.parent = auxiliary;
// Add node into auxiliary node
// Change current node as auxiliary node
auxiliary = node;
}
else
{
// visit parent node
auxiliary = auxiliary.parent;
}
}
}
public int getScore(TreeNode node)
{
if (node.child.size() == 0)
{
return 1;
}
int result = 0;
for (int i = 0; i < node.child.size(); ++i)
{
result += this.getScore(node.child.get(i));
}
if (node.parent == null)
{
return result;
}
else
{
return 2 * result;
}
}
public static void main(String[] args)
{
Score s1 = new Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

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

*/
// Test A
System.out.println(s1.getScore(s1.root));
Score s2 = new Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
System.out.println(s2.getScore(s2.root));
}
}``````

#### Output

``````12
3``````
``````// Include header file
#include <iostream>

#include <string>

#include <vector>

using namespace std;
/*
C++ program for
Score of parentheses using tree
*/
class TreeNode
{
public: TreeNode *parent;
vector < TreeNode *> child;
TreeNode()
{
this->parent = NULL;
}
};
class Score
{
public: TreeNode *root;
Score(string text)
{
this->root = new TreeNode();
this->constructTree(text);
}
void constructTree(string text)
{
TreeNode *auxiliary = this->root;
for (int i = 0; i < text.length(); ++i)
{
if (auxiliary == NULL)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (text[i] == '(')
{
// Create new node of tree
TreeNode *node = new TreeNode();
// Set parent
node->parent = auxiliary;
// Add node into auxiliary node
auxiliary->child.push_back(node);
// Change current node as auxiliary node
auxiliary = node;
}
else
{
// visit parent node
auxiliary = auxiliary->parent;
}
}
}
int getScore(TreeNode *node)
{
if (node->child.size() == 0)
{
return 1;
}
int result = 0;
for (int i = 0; i < node->child.size(); ++i)
{
result += this->getScore(node->child.at(i));
}
if (node->parent == NULL)
{
return result;
}
else
{
return 2 *result;
}
}
};
int main()
{
Score *s1 = new Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 *( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
cout << s1->getScore(s1->root) << endl;
Score *s2 = new Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
cout << s2->getScore(s2->root) << endl;
return 0;
}``````

#### Output

``````12
3``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Score of parentheses using tree
*/
public class TreeNode
{
public TreeNode parent;
public List < TreeNode > child;
public TreeNode()
{
this.parent = null;
this.child = new List < TreeNode > ();
}
}
public class Score
{
public TreeNode root;
public Score(String text)
{
this.root = new TreeNode();
this.constructTree(text);
}
public void constructTree(String text)
{
TreeNode auxiliary = this.root;
for (int i = 0; i < text.Length; ++i)
{
if (auxiliary == null)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (text[i] == '(')
{
// Create new node of tree
TreeNode node = new TreeNode();
// Set parent
node.parent = auxiliary;
// Add node into auxiliary node
// Change current node as auxiliary node
auxiliary = node;
}
else
{
// visit parent node
auxiliary = auxiliary.parent;
}
}
}
public int getScore(TreeNode node)
{
if (node.child.Count == 0)
{
return 1;
}
int result = 0;
for (int i = 0; i < node.child.Count; ++i)
{
result += this.getScore(node.child[i]);
}
if (node.parent == null)
{
return result;
}
else
{
return 2 * result;
}
}
public static void Main(String[] args)
{
Score s1 = new Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
Console.WriteLine(s1.getScore(s1.root));
Score s2 = new Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
Console.WriteLine(s2.getScore(s2.root));
}
}``````

#### Output

``````12
3``````
``````package main
import "fmt"
/*
Go program for
Score of parentheses using tree
*/
type TreeNode struct {
parent * TreeNode
child  [] *TreeNode
}
func getTreeNode() * TreeNode {
var me *TreeNode = &TreeNode {}
me.parent = nil
me.child = make([]*TreeNode,0)
return me
}
type Score struct {
root * TreeNode
}
func getScore(text string) * Score {
var me *Score = &Score {}
me.root = getTreeNode()
me.constructTree(text)
return me
}
func(this Score) constructTree(text string) {
var auxiliary * TreeNode = this.root
for i := 0 ; i < len(text) ; i++ {
if auxiliary == nil {
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return
}
if text[i] == '(' {
// Create new node of tree
var node * TreeNode = getTreeNode()
// Set parent
node.parent = auxiliary
// Add node into auxiliary node
auxiliary.child = append(auxiliary.child, node)
// Change current node as auxiliary node
auxiliary = node
} else {
// visit parent node
auxiliary = auxiliary.parent
}
}
}
func(this Score) getScore(node * TreeNode) int {
if len(node.child) == 0 {
return 1
}
var result int = 0
for i := 0 ; i < len(node.child) ; i++ {
result += this.getScore(node.child[i])
}
if node.parent == nil {
return result
} else {
return 2 * result
}
}
func main() {
var s1 * Score = getScore("(((()))()())")
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
fmt.Println(s1.getScore(s1.root))
var s2 * Score = getScore("()()()")
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
fmt.Println(s2.getScore(s2.root))
}``````

#### Output

``````12
3``````
``````<?php
/*
Php program for
Score of parentheses using tree
*/
class TreeNode
{
public \$parent;
public \$child;
public	function __construct()
{
\$this->parent = NULL;
\$this->child = array();
}
}
class Score
{
public \$root;
public	function __construct(\$text)
{
\$this->root = new TreeNode();
\$this->constructTree(\$text);
}
public	function constructTree(\$text)
{
\$auxiliary = \$this->root;
for (\$i = 0; \$i < strlen(\$text); ++\$i)
{
if (\$auxiliary == NULL)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (\$text[\$i] == '(')
{
// Create new node of tree
\$node = new TreeNode();
// Set parent
\$node->parent = \$auxiliary;
// Add node into auxiliary node
\$auxiliary->child[] = \$node;
// Change current node as auxiliary node
\$auxiliary = \$node;
}
else
{
// visit parent node
\$auxiliary = \$auxiliary->parent;
}
}
}
public	function getScore(\$node)
{
if (count(\$node->child) == 0)
{
return 1;
}
\$result = 0;
for (\$i = 0; \$i < count(\$node->child); ++\$i)
{
\$result += \$this->getScore(\$node->child[\$i]);
}
if (\$node->parent == NULL)
{
return \$result;
}
else
{
return 2 * \$result;
}
}
}

function main()
{
\$s1 = new Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
echo(\$s1->getScore(\$s1->root).
"\n");
\$s2 = new Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
echo(\$s2->getScore(\$s2->root).
"\n");
}
main();``````

#### Output

``````12
3``````
``````/*
Node JS program for
Score of parentheses using tree
*/
class TreeNode
{
constructor()
{
this.parent = null;
this.child = [];
}
}
class Score
{
constructor(text)
{
this.root = new TreeNode();
this.constructTree(text);
}
constructTree(text)
{
var auxiliary = this.root;
for (var i = 0; i < text.length; ++i)
{
if (auxiliary == null)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (text.charAt(i) == '(')
{
// Create new node of tree
var node = new TreeNode();
// Set parent
node.parent = auxiliary;
// Add node into auxiliary node
auxiliary.child.push(node);
// Change current node as auxiliary node
auxiliary = node;
}
else
{
// visit parent node
auxiliary = auxiliary.parent;
}
}
}
getScore(node)
{
if (node.child.length == 0)
{
return 1;
}
var result = 0;
for (var i = 0; i < node.child.length; ++i)
{
result += this.getScore(node.child[i]);
}
if (node.parent == null)
{
return result;
}
else
{
return 2 * result;
}
}
}

function main()
{
var s1 = new Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
console.log(s1.getScore(s1.root));
var s2 = new Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
console.log(s2.getScore(s2.root));
}
main();``````

#### Output

``````12
3``````
``````#    Python 3 program for
#    Score of parentheses using tree
class TreeNode :
def __init__(self) :
self.parent = None
self.child = []

class Score :
def __init__(self, text) :
self.root = TreeNode()
self.constructTree(text)

def constructTree(self, text) :
auxiliary = self.root
i = 0
while (i < len(text)) :
if (auxiliary == None) :
#  Means that parentheses not valid
#  That is is an unbalanced parentheses.
return

if (text[i] == '(') :
#  Create new node of tree
node = TreeNode()
#  Set parent
node.parent = auxiliary
#  Add node into auxiliary node
auxiliary.child.append(node)
#  Change current node as auxiliary node
auxiliary = node
else :
#  visit parent node
auxiliary = auxiliary.parent

i += 1

def getScore(self, node) :
if (len(node.child) == 0) :
return 1

result = 0
i = 0
while (i < len(node.child)) :
result += self.getScore(node.child[i])
i += 1

if (node.parent == None) :
return result
else :
return 2 * result

def main() :
s1 = Score("(((()))()())")
#    Parentheses :  (((()))()())
#    (((()))()())
#    Here :
#        ((())) = 4
#            () = 1
#            () = 1
#    ----------------------------------
#    2 * ( 4 + 1 + 1)     = 12
#   ------------------------------------
#  Test A
print(s1.getScore(s1.root))
s2 = Score("()()()")
#    Parentheses :  ()()()
#                    - - -
#                   1+1+1  = 3
#  Test B
print(s2.getScore(s2.root))

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

#### Output

``````12
3``````
``````#    Ruby program for
#    Score of parentheses using tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :parent, :child
def initialize()
self.parent = nil
self.child = []
end

end

class Score
# Define the accessor and reader of class Score
attr_accessor :root
def initialize(text)
self.root = TreeNode.new()
self.constructTree(text)
end

def constructTree(text)
auxiliary = self.root
i = 0
while (i < text.length)
if (auxiliary == nil)
#  Means that parentheses not valid
#  That is is an unbalanced parentheses.
return
end

if (text[i] == '(')
#  Create new node of tree
node = TreeNode.new()
#  Set parent
node.parent = auxiliary
#  Add node into auxiliary node
auxiliary.child.push(node)
#  Change current node as auxiliary node
auxiliary = node
else

#  visit parent node
auxiliary = auxiliary.parent
end

i += 1
end

end

def getScore(node)
if (node.child.length == 0)
return 1
end

result = 0
i = 0
while (i < node.child.length)
result += self.getScore(node.child[i])
i += 1
end

if (node.parent == nil)
return result
else

return 2 * result
end

end

end

def main()
s1 = Score.new("(((()))()())")
#    Parentheses :  (((()))()())
#    (((()))()())
#    Here :
#        ((())) = 4
#            () = 1
#            () = 1
#    ----------------------------------
#    2 * ( 4 + 1 + 1)     = 12
#   ------------------------------------
#  Test A
print(s1.getScore(s1.root), "\n")
s2 = Score.new("()()()")
#    Parentheses :  ()()()
#                    - - -
#                   1+1+1  = 3
#  Test B
print(s2.getScore(s2.root), "\n")
end

main()``````

#### Output

``````12
3
``````
``````import scala.collection.mutable._;
/*
Scala program for
Score of parentheses using tree
*/
class TreeNode(var parent: TreeNode,
var child: ArrayBuffer[TreeNode])
{
def this()
{
this(null, new ArrayBuffer[TreeNode]())
}
}
class Score(var root: TreeNode)
{
def this(text: String)
{
this(new TreeNode());
this.constructTree(text);

}
def constructTree(text: String): Unit = {
var auxiliary: TreeNode = this.root;
var i: Int = 0;
while (i < text.length())
{
if (auxiliary == null)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (text.charAt(i) == '(')
{
// Create new node of tree
var node: TreeNode = new TreeNode();
// Set parent
node.parent = auxiliary;
// Add node into auxiliary node
auxiliary.child += node;
// Change current node as auxiliary node
auxiliary = node;
}
else
{
// visit parent node
auxiliary = auxiliary.parent;
}
i += 1;
}
}
def getScore(node: TreeNode): Int = {
if (node.child.size == 0)
{
return 1;
}
var result: Int = 0;
var i: Int = 0;
while (i < node.child.size)
{
result += this.getScore(node.child(i));
i += 1;
}
if (node.parent == null)
{
return result;
}
else
{
return 2 * result;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var s1: Score = new Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
println(s1.getScore(s1.root));
var s2: Score = new Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
println(s2.getScore(s2.root));
}
}``````

#### Output

``````12
3``````
``````import Foundation;
/*
Swift 4 program for
Score of parentheses using tree
*/
class TreeNode
{
var parent: TreeNode? ;
var child: [TreeNode? ];
init()
{
self.parent = nil;
self.child = [TreeNode?]();
}
}
class Score
{
var root: TreeNode? ;
init(_ text: String)
{
self.root = TreeNode();
self.constructTree(Array(text));
}
func constructTree(_ text: [Character])
{
var auxiliary: TreeNode? = self.root;
var i: Int = 0;
while (i < text.count)
{
if (auxiliary == nil)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (text[i] == "(")
{
// Create new node of tree
let node: TreeNode = TreeNode();
// Set parent
node.parent = auxiliary;
// Add node into auxiliary node
auxiliary!.child.append(node);
// Change current node as auxiliary node
auxiliary = node;
}
else
{
// visit parent node
auxiliary = auxiliary!.parent;
}
i += 1;
}
}
func getScore(_ node: TreeNode? ) -> Int
{
if (node!.child.count == 0)
{
return 1;
}
var result: Int = 0;
var i: Int = 0;
while (i < node!.child.count)
{
result += self.getScore(node!.child[i]);
i += 1;
}
if (node!.parent == nil)
{
return result;
}
else
{
return 2 * result;
}
}
}
func main()
{
let s1: Score = Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
print(s1.getScore(s1.root));
let s2: Score = Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
print(s2.getScore(s2.root));
}
main();``````

#### Output

``````12
3``````
``````/*
Kotlin program for
Score of parentheses using tree
*/
class TreeNode
{
var parent: TreeNode ? ;
var child: MutableList < TreeNode >;
constructor()
{
this.parent = null;
this.child = mutableListOf < TreeNode > ();
}
}
class Score
{
var root: TreeNode ? ;
constructor(text: String)
{
this.root = TreeNode();
this.constructTree(text);
}
fun constructTree(text: String): Unit
{
var auxiliary: TreeNode ? = this.root;
var i: Int = 0;
while (i < text.length)
{
if (auxiliary == null)
{
// Means that parentheses not valid
// That is is an unbalanced parentheses.
return;
}
if (text.get(i) == '(')
{
// Create new node of tree
val node: TreeNode = TreeNode();
// Set parent
node.parent = auxiliary;
// Add node into auxiliary node
// Change current node as auxiliary node
auxiliary = node;
}
else
{
// visit parent node
auxiliary = auxiliary.parent;
}
i += 1;
}
}
fun getScore(node: TreeNode ? ): Int
{
if (node!!.child.size == 0)
{
return 1;
}
var result: Int = 0;
var i: Int = 0;
while (i < node.child.size)
{
result += this.getScore(node.child[i]);
i += 1;
}
if (node.parent == null)
{
return result;
}
else
{
return 2 * result;
}
}
}
fun main(args: Array < String > ): Unit
{
val s1: Score = Score("(((()))()())");
/*
Parentheses :  (((()))()())

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

Here :
((())) = 4
() = 1
() = 1
----------------------------------
2 * ( 4 + 1 + 1)     = 12
------------------------------------
*/
// Test A
println(s1.getScore(s1.root));
val s2: Score = Score("()()()");
/*
Parentheses :  ()()()
- - -
1+1+1  = 3
*/
// Test B
println(s2.getScore(s2.root));
}``````

#### Output

``````12
3``````

## Time Complexity

• The `constructTree` method iterates through the input string once, taking O(n) time, where n is the length of the input string.
• The `getScore` method traverses the constructed tree, visiting each node once, also taking O(n) time.
• Overall, the time complexity of the code is O(n).

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