Assume that a class ExpressionTree has a data field that is a BinaryTree. Write

Question

Assume that a class ExpressionTree has a data field that is a BinaryTree. Write an instance method to evaluate an expression stored in a binary tree whose nodes contain either integer values ( stored in Integer objects) or operators ( stored in Character objects). Your method should implement the following algorithm.

Algorithm to Evaluate an Expression Tree:
1. if the root node is an Integer object
2. Return the integer value.
3. else if the root node is a Character object
4. Let leftVal be the value obtained by recursively applying this algorithm to
the left subtree.
5. Let rightVal be the value obtained by recursively applying this algorithm to
the right subtree.
6. Return the value obtained by applying the operator in the root node to leftVal
and rightVal.

Explanation / Answer

public class ExpressionTree { private Node root; public Integer evaluateTree() { if (root == null) return null; else return evaluateTreeRecursive(root); } private Integer evaluateTreeRecursive(Node root) { // if invalid tree return null if (root == null) return null; // if integer at root return directly if (root.getData() instanceof Integer) return (Integer) root.getData(); // if operation at root compute left result then right result // then current result if (root.getData() instanceof Character) { // invalid tree if (root.getLeft() == null || root.getRight() == null) return null; // get result from left and right Integer leftResult = evaluateTreeRecursive(root.getLeft()); Integer rightResult = evaluateTreeRecursive(root.getRight()); // get current operation Character operation = (Character) root.getData(); // perform the operation switch (operation) { case '+': return leftResult + rightResult; case '-': return leftResult - rightResult; case '*': return leftResult * rightResult; case '/': return leftResult / rightResult; case '^': Integer result = 1; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.