Write a C++ program that creates and populate a tree for an arithmetic expression. Then it should perform an in-order and a post-order traversal on the tree. The input of the program will be a text file with the arithmetic expressions in RPN. The output of the program will be a printout of the arithmetic expression written out in both in-fix and post-fix (Reverse Polish) notations. The program does not need to compute the value of the expressions, only print them out.
Note: - The in-fix notation must have all brackets in the right placesi.e. the in-order traversal must be modified to achieve this.
- The post-fix print out is useful for debugging purposes, as it should look like the original text file.
- You need to use a stack that is able to store Tree pointers. You can modify the Stack we developed in class, or use STL.
Remember that you can use the following algorithm to build the tree out of a file with the post-fix notation:
An algorithm to construct an arithmetic tree
Read in an expression that is already in post-fix notation.
Tree *T1, *T2, *T; Stack S; //note that S is a stack of pointers to trees
while (expression continues) {
x = next item from the expression
if (x is a number) { S.Push(new Tree(x, NULL, NULL)); }
if (x is an operator) {
T1 = S.Top(); S.Pop();
T2 = S.Top(); S.Pop();
S.Push(new Tree(x, T2, T1)); //note order of T2 and T1
}
}
T = S.Top();
Submit a one file code on Stream by 6pm on Wednesday 2 of May 2013. Your name and ID number must appear on top of the file as comments. If you are working in a group then all names and IDs must appear on top of the file as comments. Submit one file per group on Stream.