Score of Parentheses using Tree | Customized tree class or struct , contains all required methods . ; Function to add a child into the list of children ; Function to change the parent pointer to the node passed ; Function to return the parent of the current node ; Function to compute the score recursively . ; Base case ; Adds scores of all children ; Function to create the tree structure ; Creating a node for every " ( ) " ; If we find " ( " we add a node as a child ; On finding " ) " which confirms that a pair is closed , we go back to the parent ; Driver code ; Generating the tree ; Computing the score
class TreeNode : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . parent = None NEW_LINE self . children = [ ] NEW_LINE DEDENT def addChild ( self , node ) : NEW_LINE INDENT self . children . append ( node ) ; NEW_LINE DEDENT def setParent ( self , node ) : NEW_LINE INDENT self . parent = node ; NEW_LINE DEDENT def getParent ( self ) : NEW_LINE INDENT return self . parent ; NEW_LINE DEDENT def computeScore ( self ) : NEW_LINE INDENT if ( len ( self . children ) == 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT res = 0 ; NEW_LINE for curr in self . children : NEW_LINE INDENT res += curr . computeScore ( ) ; NEW_LINE DEDENT if ( self . parent == None ) : NEW_LINE INDENT return res ; NEW_LINE DEDENT else : NEW_LINE INDENT return 2 * res ; NEW_LINE DEDENT DEDENT DEDENT def computeTree ( s ) : NEW_LINE INDENT current = TreeNode ( ) ; NEW_LINE root = current ; NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT if ( s [ i ] == ' ( ' ) : NEW_LINE INDENT child = TreeNode ( ) ; NEW_LINE child . setParent ( current ) ; NEW_LINE current . addChild ( child ) ; NEW_LINE current = child ; NEW_LINE DEDENT else : NEW_LINE INDENT current = current . getParent ( ) ; NEW_LINE DEDENT DEDENT return root ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = " ( ( ) ( ( ) ) ) " ; NEW_LINE root = computeTree ( s ) ; NEW_LINE print ( root . computeScore ( ) ) NEW_LINE DEDENT