Solve usnig C++
The first step in building a parse tree is to break up theexpression string into a list of tokens. There are four differentkinds of tokens to consider: left parentheses, right parentheses,operators, and operands. We know that whenever we read a leftparenthesis we are starting a new expression, and hence we shouldcreate a new tree to correspond to that expression. Conversely,whenever we read a right parenthesis, we have finished anexpression. We also know that operands are going to be leaf nodesand children of their operators. Finally, we know that everyoperator is going to have both a left and a right child.
Using the information from above, we can define four rules asfollows: 1. If the current token is a ‘(‘, add a new node as theleft child of the current node, and descend to the left child. 2.If the current token is in the list [‘+’,’-‘,’/’,’*’], set the rootvalue of the current node to the operator represented by thecurrent token. Add a new node as the right child of the currentnode and descend to the right child. 3. If the current token is anumber, set the root value of the current node to the number andreturn to the parent. 4. If the current token is a ‘)’, go to theparent of the current node.