figure parse tree for (( ( )replace an entire subtree with one node once we have evaluated the expressions in the children applying this replacement procedure gives us the simplified tree shown in figure simplified parse tree for (( ( )in the rest of this section we are going to examine parse trees in more detail in particular we will look at how to build parse tree from fully parenthesized mathematical expression how to evaluate the expression stored in parse tree how to recover the original mathematical expression from parse tree the first step in building parse tree is to break up the expression string into list of tokens there are four different kinds of tokens to considerleft parenthesesright parenthesesoperatorsand operands we know that whenever we read left parenthesis we are starting new expressionand hence we should create new tree to correspond to that expression converselywhenever we read right parenthesiswe have finished an expression we also know that operands are going to be leaf nodes and children of their operators finallywe know that every operator is going to have both left and right child using the information from above we can define four rules as follows if the current token is '('add new node as the left child of the current nodeand descend to the left child if the current token is in the list ['+','-','/','*']set the root value of the current node to the operator represented by the current token add new node as the right child of the current node and descend to the right child if the current token is numberset the root value of the current node to the number and return to the parent if the current token is ')'go to the parent of the current node binary tree applications