The first step in building a parse tree is to break up the expression string into a list of tokens. There are four different kinds of tokens to consider: left parentheses, right parentheses, operators, and operands. We know that whenever we read a left parenthesis we are starting a new expression, and hence we should create a new tree to correspond to that expression. Conversely, whenever we read a right parenthesis, we have finished an expression. We also know that operands are going to be leaf nodes and children of their operators. Finally, we know that every operator is going to have both a left and a right child. Using the information from above, we can define four rules as follows: 1. If the current token is a '(', add a new node as the left child of the current node, and descend to the left child. 2. 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 a new node as the right child of the current node and descend to the right child. 3. If the current token is a number, set the root value of the current node to the number and return to the parent. 4. If the current token is a ')', go to the parent of the current node.
The first step in building a parse tree is to break up the expression string into a list of tokens. There
are four different kinds of tokens to consider: left parentheses, right parentheses, operators, and
operands. We know that whenever we read a left parenthesis we are starting a new expression, and
hence we should create a new tree to correspond to that expression. Conversely, whenever we read
a right parenthesis, we have finished an expression. We also know that operands are going to be
leaf nodes and children of their operators. Finally, we know that every operator is going to have
both a left and a right child.
Using the information from above, we can define four rules as follows:
1. If the current token is a '(', add a new node as the left child of the current node, and descend
to the left child.
2. 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 a new node as the right child of the current
node and descend to the right child.
3. If the current token is a number, set the root value of the current node to the number and
return to the parent.
4. If the current token is a ')', go to the parent of the current node.
Note: use DSA concepts with C++
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
