Score of Parentheses using Tree | C ++ 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
#include <iostream> NEW_LINE #include <vector> NEW_LINE using namespace std ; class TreeNode { TreeNode * parent = NULL ; vector < TreeNode * > children ; public : void addChild ( TreeNode * node ) { children . push_back ( node ) ; } void setParent ( TreeNode * node ) { parent = node ; } TreeNode * getParent ( ) { return parent ; } 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 ; } } ; TreeNode * computeTree ( string s ) { TreeNode * current = new TreeNode ( ) ; TreeNode * root = current ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) { if ( s [ i ] == ' ( ' ) { TreeNode * child = new TreeNode ( ) ; child -> setParent ( current ) ; current -> addChild ( child ) ; current = child ; } else { current = current -> getParent ( ) ; } } return root ; } int main ( ) { string s = " ( ( ) ( ( ) ) ) " ; TreeNode * root = computeTree ( s ) ; cout << root -> computeScore ( ) ; return 0 ; }