In this project you will define your own format for parsing a mathematical expression into a Binary Expression Tree. A binary expression tree is a specific kind of a binary tree used to represent expressions. These trees can represent expressions that contain numbers, variables, and unary and binary operators. To simplify our project, we will only deploy binary operators and numbers.
An example of algebraic expression ((2 + 3) * (1 + (5 - 4)) is constructed in Fig1. see image.
The goal of this project is to create a simple Expression Tree, or a Parse Tree, using binary tree data structure.
You will be creating two classes for this project: BinaryTree and ExpressionTree. The idea is to use the BinaryTree class as the base data structure, the ExpressionTree as the inherited class.
You will be creating a BinaryTree class.
The following structure is a sample code of the node type for building the BinaryTree nodes/vertices. You may need to modify the node structure according to your program needs.
template< class T >
struct Node {
T data; //You may simply use char for this project, instead of using template
2
Node* left;
Node* right;
} ;
Please create related member variables and methods (such as destructor) for the class.
We will be creating Algebraic Binary Expression Tree.
Please create a class ExpressionTree that inherits BinaryTree.
To simplify the parse tree creation, we use parenthesis to group any binary operator operations. For example: 2+3 *5. We will write as either ((2 + 3) * 5) or (2 + (3 * 5)), in this way, we can treat each pair of parenthesis as a recursive function. Yet in general, the parenthesis will make the parsing a lot easier (so that we don't have to worry about operator precedence). You may use either iterative approach or recursive approach to build the parse tree.
Binary operators allowed in the project: +, -, *, /
Binary operands allowed in the project: number literals (you may use only single digit 0-9).
Based on the parenthesis order, each node should be added in the Expression Tree in an ordered fashion.
The class should have, but not limited to, the following member methods
1. expressionToTree() //to convert an algebra expression to Expression Tree
2. treeToExpression() // to convert an Expression Tree to algebraic expression. You may use inorder (infix) traversal to do the job. (See related algorithm on the right)
Algorithm infix (tree)
/*Print the infix expression for an expression tree.
Pre: tree is a pointer to an expression tree
Post: the infix expression has been printed */
if (tree not empty)
__if(tree token is operator)
____print (open parenthesis)
__end if
__infix (tree left subtree)
__print (tree token)
__infix (tree right subtree)
__if (tree token is operator)
____print (close parenthesis)
__end if
end if
end infix
We may define four rules for node insertion as follows (this is the iterative approach):
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.
Please create a UML diagram for your projects including all classes and their members, as well as the relationship among classes