Objective:
Write a C program that will accept an infix expression from the user, build an expression tree using the algorithm described in class and then traverse the tree recursively three times to produce the prefix, infix and postfix expressions. Notice that the infix expression produced from the tree should contain only necessary parentheses.
Specification:
Operands will be represented by single uppercase letters (A..Z). Operators will include (+, -, *, /, %).
Spaces may be included anywhere in the infix expression. They should not be included in result expressions.
You may assume that the input expression will not exceed 80 characters.
The operands should appear in the same order in the output as the input.
The program should error test for the following conditions: An illegal character or unmatched parentheses.
(Note: legal characters are operands, operators and spaces.)
Algorithm:
This is a rather complex program that uses a number of data structures. For example, you might choose to use a queue, two stacks and a series of trees. It will be critical for you to make decisions as to how you are going to implement your data structures. Once you begin generating code it will be difficult and time consuming to change data structures.
You may organize your code as you desire. For example, you might choose to include the entire program in a single (.c) file or you might choose to include several (.c) and several (.h) files.
Sample Runs:
Please enter an Infix expression -- A + (B - C * D) / E
PREFIX : +A/-B*CDE
INFIX : A+(B-C*D)/E
POSTFIX : ABCD*-E/+
Please enter an Infix expression -- A + ( B - C
Unmatched left parenthesis.
