Reading Prefix Expressions: Part A - Using an Iterator
An arithmetic expression in prefix form can be easily read into a binary tree
of characters, and then output in infix or postfix using an inorder or
postorder traversal.
There are two ways to read a prefix expression into a binary tree. The first
algorithm uses an iterator:
do {
Read character
If the tree is empty
Insert the root node with this character
If the character is an operator (one of *, /, +, or -)
Set the iterator to the root
Else If there is no left offspring from the iterator node
Add a left offspring from the iterator node with this character
If the character is an operator (one of *, /, +, or -)
Set the iterator to the new left offspring
Else Add a right offspring from the iterator node with this character
If the character is an operator (one of *, /, +, or -)
Set the iterator to the new right offspring
Else While the iterator node exists and it has a right offspring
Move the iterator up to its parent
} While the iterator node exists
Use the YABTI binary tree class in
binarytreeclass.h and
binarytreeclass.cpp
to implement the above algorithm, and to output the input expression in
perfix, infix, and postfix form.
As a first test, if you input the prefix expression +*AB-C/DE
the three outputs should be:
+ * A B - C / D E
A * B + C - D / E
A B * C D E / - +
Reading Prefix Expressions: Part B - Using Recursion
The second algorithm uses recursion to read the prefix expression into a
binary tree. Work out and implement this algorithm.
Answer