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:
        return totalScore

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

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

Code Solution

• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

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));
	}
}

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;
}

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));
	}
}

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))
}

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

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

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

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

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));
	}
}

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

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));
}

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