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:
- An empty string or a pair of empty parentheses has a score of 1.
- If S is a valid string of parentheses, then "(S)" has a score of 2 * score(S).
- 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
- Create a TreeNode class with parent and child references.
- Create a Score class with root as its instance variable and two main methods:
constructTree
andgetScore
. - 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.
- 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).
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