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 COSC240_P4_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 COSC240_P4_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 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. */ 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 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 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; } }