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; }

}