Java code

1. Implement MyExpressionTree. MyExpressionTree should inherit MyBinaryTree and implement certain additional methods. In this project you will decide what additional methods need to be added into MyExpressionTree. (Hint: You should also override and/or modify some methods in the MyBinaryTree class to get the output as required in the following specifications.) 2. Create a Project4 class under the project package. 3. In the Project4 class you will create a static void test( ) method. In this test method you will do the following: a. Utilize the MyStack and MyDeque classes to build an expression tree based on an infix expression involve single digit integer number, +, -, *, /, %, and together with ( ). b. The infix expressions are located in a file named COSC241_P2_Input.txt. Each line contains an infix expression (whitespaces and empty lines should be ignored.). c. After you build the expression tree for each infix expression, you will print out the expression tree with preorder, inorder, and postorder traversal, respectively. Also, you will evaluate the expression based on the expression tree (Do not use what you have used in the last project for the evaluation part.) and print out the evaluation result. d. All print outs should be written into a file named COSC241_P2_Output_.txt. e. Sample input and output files are provided. f. The sample input file is by no mean listing all testing cases. You have to add additional testing cases to the input file to test your program completely. g. The input and output files should be located in the folder where your project folder is located (i.e. these io files and your project folder are sitting next to each other). When you open files for read and write you cannot use an absolute file path but have to use a relative file path. After you finished your program make a copy of your program folder and try to run it on another computer to see whether it still works. h. You will not submit any input or output files. Your program will be tested with another input file given the same format. 4. Under the main package, in the Main class, remove the contents of the main method we have added in the last assignment and do the following: Project2.test();

public class MyStack {

public SLListNode top;

/**

* Default constructor

*/

public MyStack()

{

top = null;

}

/**

* Clears the stack

*/

public void clear()

{

top = null;

}

/**

* Check whether the stack is empty.

* @return true if empty false otherwise.

*/

public boolean isEmpty()

{

return top == null;

}

/**

* Removes the top object of the stack and return the removed

object.

* @return the object which is popped

*/

public Object pop()

{

if(isEmpty())

{

return null;

}

Object temp = top.data;

top = top.next;

return temp;

}

/**

* Adds a node to the top of the stack.

* @param the element to be added as the data of the new node.

*/

public void push(Object element)

{

top= new SLListNode(element, top);

}

/**

* Returns the data contained in the top node of the stack.

* @return the top data object.

*/

public Object top()

{

if(isEmpty())

{

return null;

}

return top.data;

}

/**

* Converts the current stack into a string from top to bottom.

* @return the result string

*/

public String toString()

{

String out = "The Stack contains: ";

SLListNode ref = top;

if(isEmpty())

return "0 nodes.";

else

out += "top ->\t";

while(ref.next != null)

{

out += ref.data + "\t->\t";

ref = ref.next;

}

out += ref.data +"\t->null"; //Add the last node.

return out;

}

}

______

public class MyDeque extends DLList {

/**

* Default constructor.

*/

public MyDeque()

{

super();

}

/**

* This method returns the Object at the front of the deque.

*

* @return the Object at the front of the deque

*/

public Object front() {

if(head == null)

return null;

return head.data;

}

/**

* This method returns the Object at the back of the deque.

*

* @return the Object at the back of the deque

*/

public Object back() {

if(head == null)

return null;

return tail.data;

}

/**

* This method inserts an Object at the back of the deque.

*

* @param element the Object to be inserted

*/

public void insertBack(Object element) {

append(element);

}

/**

* This method removes the Object at the back of the deque and

returns it.

*

* @return the Object that was removed from the back of the deque

*/

public Object removeBack() {

if(head == null)

return null;

Object temp = back();

if(head == tail) {

head = tail = null;

return temp;

}

tail = tail.prev;

tail.next = null;

return temp;

}

/**

* This method inserts the Object at the head of the deque.

*

* @param the Object to be inserted at the head of the deque

*/

public void insertFront(Object element) {

insert(element);

}

/**

* This method removes the Object at the head of the deque and

returns it.

*

* @return the Object that was removed from the head of the deque

*/

public Object removeFront() {

if(head == null)

return null;

Object temp = front();

if(head == tail) {

head = tail = null;

return temp;

}

head = head.next;

head.prev = null;

return temp;

}

/**

* This method returns the deque in a String form.

*

* @return the String form of the deque

*/

public String toString() {

String out = "The deque contains: ";

DLListNode ref = head;

if(head == null)

return out + "0 nodes.";

else

out += "front -->\t";

while(ref != tail)

{

out += ref.data + "\t<-->\t";

ref = ref.next;

}

out += ref.data + "\t<-- back";

return out;

}

}

______

public class MyExpressionTree extends MyBinaryTree {

public MyExpressionTree() { root = null; }

public MyExpressionTree(MyBinaryTreeNode rt) { root = rt; }

public static int evaluate(MyBinaryTreeNode rt) { if (rt == null) { return -1; }

if (rt.left == null && rt.right == null) { return Character.getNumericValue((Character) rt.data); }

switch ((Character) rt.data) { case '-': return evaluate(rt.left) - evaluate(rt.right); case '+': return evaluate(rt.left) + evaluate(rt.right); case '*': return evaluate(rt.left) * evaluate(rt.right); case '/': return evaluate(rt.left) / evaluate(rt.right); case '%': return evaluate(rt.left) % evaluate(rt.right);

}

return -1; }

public String preorderTraversal() { return preorderHelper(root) + " "; }

private String preorderHelper(MyBinaryTreeNode rt) { if (rt == null) { return ""; } return rt.data + " " + preorderHelper(rt.left) + " " + preorderHelper(rt.right); }

public String inorderTraversal() { return inorderHelper(root) + " "; }

private String inorderHelper(MyBinaryTreeNode rt) { if (rt == null) { return ""; } return inorderHelper(rt.left) + " " + rt.data + " " + inorderHelper(rt.right); }

public String postorderTraversal() { return postorderHelper(root) + " "; }

private String postorderHelper(MyBinaryTreeNode rt) { if (rt == null) { return ""; } return postorderHelper(rt.left) + " " + postorderHelper(rt.right) + " " + rt.data; }

}

________

public abstract class MyBinaryTree

{

public MyBinaryTreeNode root;

/**

* Remove all the tree nodes.

*/

public void clear()

{

root = null;

}

/**

* Check whether the tree is empty.

* @return true if the tree contains no nodes, false otherwise.

*/

public boolean isEmpty()

{

return root == null;

}

/**

* Get the number of nodes in the tree.

* @return The number of nodes in the tree.

*/

public int size()

{

return sizeHelper(root);

}

/*

* The private helper method for size().

* Get the number of nodes in the tree rooted at r.

* @param rt The current root of the tree.

* @return The number of nodes in the tree.

*/

private int sizeHelper(MyBinaryTreeNode rt)

{

if (rt == null)

return 0;

return sizeHelper(rt.left) + sizeHelper(rt.right) + 1;

}

/**

* Get the height of the tree.

* @return The height of the tree.

*/

public int height()

{

return heightHelper(root, -1);

}

/*

* The private helper method for height().

* Get the height of the subtree rooted at rt.

* @param rt The current root.

* @param ht The current height.

* @return The height of the tree.

*/

private int heightHelper(MyBinaryTreeNode rt, int ht)

{

if (rt == null)

return ht;

return Math.max(heightHelper(rt.left, ht+1),

heightHelper(rt.right, ht+1));

}

/**

* Preorder traverse the tree and print out each node.

*/

public String preorderTraversal()

{

preorderHelper(root);

System.out.println();

return "";

}

/*

* The private helper method for preorderTraversal().

*/

private void preorderHelper(MyBinaryTreeNode rt)

{

if(rt == null) return;

System.out.print("\t" + rt.data);

preorderHelper(rt.left);

preorderHelper(rt.right);

}

/**

* Inorder traverse the tree and print out each node.

*/

public String inorderTraversal()

{

inorderHelper(root);

System.out.println();

return "";

}

/*

* The private helper method for inorderTraversal().

*/

private void inorderHelper(MyBinaryTreeNode rt)

{

if(rt == null) return;

inorderHelper(rt.left);

System.out.print("\t" + rt.data);

inorderHelper(rt.right);

}

/**

* Postorder traverse the tree and print out each node.

*/

public String postorderTraversal()

{

postorderHelper(root);

System.out.println();

return "";

}

/*

* The private helper method for postorderTraversal().

*/

private void postorderHelper(MyBinaryTreeNode rt)

{

if(rt == null) return;

postorderHelper(rt.left);

postorderHelper(rt.right);

System.out.print("\t" + rt.data);

}

}

_______

public class DLList {

public DLListNode head;

public DLListNode tail;

/**

* The default constructor

*/

public DLList() {

head = tail = null;

}

/**

* This method appends an Object at the end of the list

*

* @param element the Object to be appended

*/

public void append(Object element) {

if(head == null)

{

head = tail = new DLListNode(element, null,

null);

}

else

{

tail = new DLListNode(element, tail, null);

tail.prev.next = tail;

}

}

/**

* This method inserts an Object at the beginning of the list

*

* @param element the Object to be inserted

*/

public void insert(Object element) {

if(head == null)

{

head = tail = new DLListNode(element, null,

null);

}

else

{

head = new DLListNode(element, null, head);

head.next.prev = head;

}

}

/**

* This method clears the list

*/

public void clear()

{

head = tail = null;

}

/**

* This method removes a node from the list,

* which contains the same value as the element.

*

* @param element the value to be compared to

* @return boolean false if not found, true if removed successfully

*/

public void remove(Object element)

{

if(head == null) return;

if(((Comparable)head.data).compareTo((Comparable)element)

== 0)

{//The head node is the node to be removed.

if(head == tail) //List contains one node.

{

head = tail = null;

}

else

{

head = head.next;

head.prev = null;

}

return;

}

if (head == tail)

{//The DLList contains only one node and it is not the

node to be removed.

return;

}

DLListNode ref = head.next;

while(ref != tail)

{

if(((Comparable)ref.data).compareTo((Comparable)element) == 0)

{

ref.prev.next = ref.next;

ref.next.prev = ref.prev;

return;

}

ref = ref.next;

}

if(((Comparable)tail.data).compareTo((Comparable)element)

== 0)

{//The tail node is the node to be removed.

tail = tail.prev;

tail.next = null;

}

}

/**

* This method checks whether the list is empty

*

* @return boolean true if empty, false otherwise

*/

public boolean isEmpty() {

return head == null;

}

/**

* This method returns the entire list in a String form

*

* @return the String form of the list

*/

public String toString() {

String out = "The DLList contains: ";

DLListNode ref = head;

if(head == null)

return out + "0 nodes.";

else

out += "head -->\t";

while(ref != tail)

{

out += ref.data + "\t<-->\t";

ref = ref.next;

}

out += ref.data + "\t<-- tail";

return out;

}

}

_____

public class MyBinaryTreeNode implements Comparable

{

public Object data;

public MyBinaryTreeNode left;

public MyBinaryTreeNode right;

/**

* The constructor.

* @param d The data part.

*/

public MyBinaryTreeNode(Object d)

{

data = d;

left = null;

right = null;

}

/**

* The constructor.

* @param d The data part.

* @param l Reference to the left child.

* @param r Reference to the right child.

*/

public MyBinaryTreeNode(Object d, MyBinaryTreeNode l,

MyBinaryTreeNode r)

{

data = d;

left = l;

right = r;

}

/**

* Get the string representation of the current node.

* @return The string representation

*/

public String toString()

{

return data.toString();

}

/**

* Implement the compareTo method of the Comparable interface.

* @param target The target MyBinaryTreeNode to be compared to.

* @return -1 if this < target, 1 if this > target, 0 otherwise.

*/

public int compareTo(MyBinaryTreeNode target)

{

return ((Comparable)this.data).compareTo(target.data);

}

}

______

public class MyQueue {

public SLListNode front;

public SLListNode rear;

/**

* Default constructor.

*/

public MyQueue()

{

front = rear = null;

}

/**

* Clears the queue.

*/

public void clear()

{

front = rear = null;

}

/**

* Check whether the queue is empty.

* @return true if empty false otherwise.

*/

public boolean isEmpty()

{

return front == null;

}

/**

* Append a node, which will hold the element, at the rear side of

the queue.

* @param element the data to be hold in the node.

*/

public void insertBack(Object element)

{

if(isEmpty())

{

front = rear = new SLListNode(element, null);

return;

}

rear = rear.next = new SLListNode(element, null);

}

/**

* Removes the node in the front of the queue.

*/

public Object removeFront()

{

if(front == null)

return null;

Object temp = front.data;

if(front == rear)

{

front = rear = null;

return temp;

}

front = front.next;

return temp;

}

/**

* Returns the element in the node at the front of the queue.

* @return data contained in the node.

*/

public Object front()

{

if(isEmpty())

{

return null;

}

return front.data;

}

/**

* Converts the current queue into a string front to rear.

* @return the result string

*/

public String toString()

{

String out = "The Queue contains: ";

SLListNode ref = front;

if(isEmpty())

return "0 nodes.";

else

out += "front ->\t";

while(ref.next != null)

{

out += ref.data + "\t->\t";

ref = ref.next;

}

out += ref.data +"\t->null"; //Add the last node.

return out;

}

}