Date: 2000 Apr 06
Due Thursday, 2000 Apr 13, at the beginning of class.
Read chapter 10. Sections 7.4 and and 10.4 on tree traversals may be useful for this homework.
Frequently, programmers want to use the same C++ files to produce different executable programs. For example, when developing code, it is frequently useful to print debugging messages, but, after development finishes, these debugging messages are a nuisance. Thus, the code producing the debugging messages should be conditionally included when compiling the program.
The tree debugging code uses #ifdef DEBUG and #endif to delimit the statements that should only be executed when debugging a program. #ifdef DEBUG abbreviates #if defined(DEBUG), which yields true only if the preprocessor symbol DEBUG is defined. #endif marks the end of the conditional section.
To tell the compiler that the preprocessor symbol DEBUG should be defined and thus the debugging statements should be included in the executable, compile with the -DDEBUG compiler flag. For example,
You and possibly a CS1321 classmate are to convert an infix arithmetic expression to postfix notation using a tree as an intermediary data structure. You may solve the problem in any way you desire as long as it conforms to the input and output specifications except that you may not use a stack.
Your program should read an infix arithmetic expression from the standard input and print the equivalent postfix arithmetic expression to the standard output.
Infix arithmetic expressions are recursively defined. The simplest arithmetic expression consists of a variable name or a number. More complicated infix expressions have the form
Postfix arithmetic expressions are similarly defined. The simplest expression consists of a variable name or a number. More complicated postfix expressions have the form
Infix arithmetic expressions, postfix arithmetic expressions, trees, in-order tree traversal, and postorder tree traversal are all recursively defined. Thus, most functions involving them are recursively defined.
Here is a possible sequence of steps to solve the problem:
We have provided a recursively defined Tree class and a skeleton file. Add code to the latter file to solve the problem. For more information about how to use the Tree class, see the instructions for its use and this example of its use.
We have also provided a file containing functions to print a tree. To use this code,
As for previous homeworks, working with other people during your planning phase is encouraged. For this homework, you are permitted to write the code, i.e., program, with one other person in CS1321. To learn the material, both of you should be actively involved in the programming. Failure to do so will almost certainly hurt your comprehension of the material in the rest of the course.
Each one- or two-person team of programmers should submit only its completed implementation, consisting of the file infix2postfix.cc. You do not need to send any other files. Please send only text documents, do not send Microsoft Word documents, PDF documents, HTML documents, etc. Please include both your names and email addresses at the top of your program.
We will test your program using our own input. Please be sure your code compiles without warning when using g++ -Wall -pedantic.
See the submission details for information how to email the programs. Note that the CS computer configuration was changed over spring break. If you want to receive an automated reply acknowledging your submission, please read the submission WWW page. If a team of two are in different sections, submit exactly once to one of the two permissible email addresses.