Skip to main content

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
Last updated on by Kalkicode




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.

New Comment