Write a program that reads a Prefix expression, and uses it to build an expression tree. It then traverses the tree the 3 different ways and outputs the expression in the 3 notations.
computer science
Description
Expression Trees and Recursion
Write a program that reads a Prefix expression, and uses it to build an expression tree. It then traverses the tree the 3 different ways and outputs the expression in the 3 notations. You will get a bonus mark if you include brackets in the resulting infix expression, which could be fully parenthesized (so you don’t worry about operators’ precedence).
You may assume each input expression is a valid prefix expression where the operands consist of
one digit and the operators are +, -, *, /.
Prefix expressions are easily manipulated using Recursion. The key to the recursion is that
every prefix expression is made up of an operator followed by 2 operands, and each of the
operands is itself a prefix expression. The simplest of prefix expressions is a single digit
(number).
So a pseudo-code algorithm would be:
For each character c in the prefix expression:
− if c is an operand, create a node containing it and return it as a subtree.
− if c is an operator, create a node containing it, then assign to the left subtree of that node
the result from the recursive call of the remaining subexpression, then assign to the right
subtree of that node the result from another recursive call of the remaining subexpression,
