Reference no: EM132412767

Exercise

A binary expression tree is a special type of binary tree that is used to represent expressions. A binary expression tree's leaves are operands, like constants or variable names, and other nodes contain operations. An expression tree can be evaluated applying the operator at the root to the values obtained by recursively evaluating the left and right subtrees.

The objective of this exercise is to implement an algorithm that is capable of evaluating an integer expression tree. All tree operators will have zero or two children. Integer values will appear in leaf nodes, whereas internal nodes will contain operators. In order to evaluate a tree of this kind, you can use the following recursive approach:

Let t be the expression tree If t is not null then
If t.value is operand then Return t.value
Else
A = solve (t.left) B = solve(t.right)
Return (A operator B)

You will find a code skeleton in edu.uoc.mecm.eda.bet.ExpressionTreeEvaluator that you will have to modify in order to achieve your objective.

Note that the tree constructor expects a postfix input expression which you will have to use to build the tree. In order to do so, you should use a stack as follows:

While there are characters in the postfix input expression Let c be the input character
Let t be a new tree node t = new node (c)
If c is an operand then Push (t)
Else
A = Pop() B = Pop()
t.right = A t.left = B Push (t)
At the end, the stack's last element is the tree's root node

Once you have completed the implementation, you can check it against the unit tests you can find in the ExpressionTreeEvaluatorTest class.