Score of Parentheses using Tree | Java program to find the 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
import java . util . * ; public class Main { static class TreeNode { public TreeNode parent = null ; public Vector < TreeNode > children = new Vector < TreeNode > ( ) ; public void addChild ( TreeNode node ) { children . add ( node ) ; } public void setParent ( TreeNode node ) { parent = node ; } public TreeNode getParent ( ) { return parent ; } public int computeScore ( ) { if ( children . size ( ) == 0 ) return 1 ; int res = 0 ; for ( TreeNode curr : children ) res += curr . computeScore ( ) ; if ( parent == null ) return res ; else return 2 * res ; } } static TreeNode computeTree ( String s ) { TreeNode current = new TreeNode ( ) ; TreeNode root = current ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s . charAt ( i ) == ' ( ' ) { TreeNode child = new TreeNode ( ) ; child . setParent ( current ) ; current . addChild ( child ) ; current = child ; } else { current = current . getParent ( ) ; } } return root ; } public static void main ( String [ ] args ) { String s = " ( ( ) ( ( ) ) ) " ; TreeNode root = computeTree ( s ) ; System . out . print ( root . computeScore ( ) ) ; } }