Project: Expression Trees

This project is adapted from Project 1 of Chapter 9 of the textbook. It deals with a simple kind of expression trees, in which there are two kinds of nodes:

(a) Leaf nodes, which contain a real number as their clement; and

(b) Non-leaf nodes, which have exactly two children and contain one of these characters as their element: +, -, * and /. These characters represent arithmetic operations and have usual interpretations.

Implement a class for expression trees with these operations:

(a) A constructor that builds an expression tree. It accepts a String that represents a grammatically correct expression as its sole input. Hint: refer to Chapter 6.2 and slides on evaluating expressions.

(b) A recursive method named eval that evaluates a non-empty expression tree using these rules:

i. If the tree has only one node (which must be a leaf), then eval returns the real number that is the node's clement;

ii. If the tree has more than one node and the root contains op where op is one of +, -, * and 7, then eval first evaluates the sub-trees of the root and returns the real number obtained by performing operation op on the results from evaluating the sub-trees.

(c) A recursive method named infix that output the expression represented by a non-empty expression tree to a String in infix format. A recursive method named post fix that outputs the expression represented by a non-empty expression tree in postfix format. You also need to write another class that applies the operations of the above class. Please submit

1. Analysis: test data;

2. Design:

A class invariant for each class;

• Pre/Post conditions for required operations;

• Algorithms for required operations.

3. Code;

4. Screen snapshots of test runs.

Answer rating: 100% (QA)

Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand so for example expressi... View the full answer