before writing the python codelet' look at an example of the rules outlined above in action we will use the expression ( ( )we will parse this expression into the following list of character tokens ['('' ''+''('' ''*'' ,')'')'initially we will start out with parse tree that consists of an empty root node figure illustrates the structure and contents of the parse treeas each new token is processed using figure let' walk through the example step by step create an empty tree read as the first token by rule create new node as the left child of the root make the current node this new child read as the next token by rule set the root value of the current node to and go back up the tree to the parent read as the next token by rule set the root value of the current node to and add new node as the right child the new right child becomes the current node read as the next token by rule create new node as the left child of the current node the new left child becomes the current node read as the next token by rule set the value of the current node to make the parent of the current node read as the next token by rule set the root value of the current node to and create new right child the new right child becomes the current node read as the next token by rule set the root value of the current node to make the parent of the current node read as the next token by rule we make the parent of the current node read as the next token by rule we make the parent of the current node at this point there is no parent for so we are done from the example aboveit is clear that we need to keep track of the current node as well as the parent of the current node the tree interface provides us with way to get children of nodethrough the get_left_child and get_right_child methodsbut how can we keep track of the parenta simple solution to keeping track of parents as we traverse the tree is to use stack whenever we want to descend to child of the current nodewe first push the current node on the stack when we want to return to the parent of the current nodewe pop the parent off the stack using the rules described abovealong with the stack and binarytree operationswe are now ready to write python function to create parse tree the code for our parse tree builder is presented belowdef build_parse_tree(fp_exp)fp_list fp_exp split(p_stack stack(e_tree binarytree(''p_stack push(e_treecurrent_tree e_tree for in fp_list trees and tree algorithms