Score of parentheses using tree
Here given code implementation process.
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
auxiliary.child.add(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
auxiliary.child.Add(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_reader :parent, :child
attr_accessor :parent, :child
def initialize()
self.parent = nil
self.child = []
end
end
class Score
# Define the accessor and reader of class Score
attr_reader :root
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
auxiliary.child.add(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
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