Skip to main content

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

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

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.

New Comment