write a utility that allows users to enter expression in any of the 3 representation (infix, pre or postfix) and output the same expression in the other 2 formats. The program should accept input in the following format:
"<" followed by a prefix expression
"=" " by an infix exp
">" " by a postfix exp
"Q" to quit
Upon encountering any of the 1st 3 commands, the program should input the exp, build the internal tree, and then output the same exp in the other 2 formats. Upon encountering a line starting with "Q", it should quit. Ex of suitable input:
< +BC
= (x+y)*z
< *-abc
> abc+/
Q
In exp, it should be able to handle operators "+", "-", "*" and "/", and operands consisting of any single upper or lower case letter.
You should use an expression tree as you internal representation, and you should use a recursive algorithm to manipulate it. Once you have built the ecpression tree, you can output th infix, prefix, postfix, by using in-order, pre-order and post-order traversals. Your only problem will be restoring the parentheses for the infix output. To do this, look at the left and right subtrees: if the left subtree has at its root an operator of lower priority than the operator at the current node, then it needs parentheses; if the right subtree has its root an operator of lower or equal priority than the operator at the current node, then it needs parentheses. To insert parentheses, output "(" before descending into the subtree, and output ")" after returning from the subtree.