Project 4: Converting Postfix to Infix Expression using Binary Expression Tree

Educational Objectives: Experience with binary trees, stacks, infix and postfix expressions. 

Statement of Work: Convert postfix expression to infix expression using binary expression tree. 

Deliverables: Turn in the makefile, all C++ source files and header files (i.e. all .h and .cpp files) that you may develop for this project, using the project4submit.sh script.

Setup Task:

1. Go into your cop4530 directory and create a directory named proj4.
2. Go into your proj4 directory and type the following command,
   
   cp -r ~cop4530/spring07/submitscripts/project4submti.sh .
   
   The command above will copy the submission script for Project 4 into your proj4 directory.

Project Description:

In this project, you are asked to write a program to convert postfix expression into infix expression using binary expression tree. The program accepts input from terminal, or the input is redirected from a file that contains the postfix expressions to be converted. Each line in the file (or typed by user) represents a postfix expression.

In this project, a postfix expression may contain 4 operators: multiplication (*), division (/), plus (+), and minus (-). We assume that multiplication and division have the same precedence, and plus and minus have the same precedence. Moreover, multiplication and division have higher precedence than plus and minus.

A postfix expression in this project only has single digit operands (0 - 9).

To convert a postfix expression into an infix expression using binary expression tree involves two steps. First, you need to build a binary expression tree from the postfix expression. Second, you need to print the nodes of the binary expression tree using inorder traversal of the tree.

The basic operation of building a binary expression tree from a postfix expression is similar to that of evaluating postfix expression. They both involve the use of stack to hold intermediate results. Essentially, when you encounter an operand, you create a one-node tree and push it into a stack. When you encounter an operator, you pop out the corresponding operands (the trees) from the stack, and build a new tree, and then push the new tree into the stack. After you have processed all tokens in the postfix expression, the stack has the binary expression tree. Please refer to Section 4.2.2 for building binary expression tree from postfix expression.

Note that during the conversion from postfix to infix expression, parentheses may need to be added to ensure that the infix expression has the same value as the corresponding postfix expression. The followings are a few examples of postfix expressions and the corresponding infix expressions.

Notes:

• You can use anything in C++ STL.

Extra credits:

• An extra of 10 points will be awarded for implementing evaluation of the expression tree.

Miscellaneous:

• All programs handed in will be tested by automatic plagiarism detection software.