Programming Assignments All programs must be properly documents, follow Java cod

Question

Programming Assignments All programs must be properly documents, follow Java coding practices, and include clear output that shows how you verified that your program works. 1. Linked Lists Deque Double-ended queue) Implement a nested class DoubleNode for building doubly linked lists, where each node contains a reference to the item preceding it and the item following it in the list (null ifthere is no such item). Then implement methods for the following tasks: Insert at the beginning Insert at the end Remove from the beginning Remove from the end Insert before a give node Insert after a given node Remove a given node Move to front (move an object to the front) Move to end (moved and object to the end) 2. Stacks E Arithmetic Expressions valuating Write a class ArithmeticExpressionEvaluator that evaluates an infix arithmetic expression. Do this is two steps. First, convert the infix expression to a postfix expression: create a filter InfixToPostfix that converts an arithmetic expression from infix to postfix. Second, evaluate the postfix expression: write a postfix evaluator EvaluatePostfix that takes a postfix expression, evaluates it and print the value. Your program should print the infix expression, postfix expression, and the final result. 3. Union-Find Maze Write a program that generates mazes of arbitrary size using the union-find algorithm. A simple algorithm to generate the maze is to start by creating an N x M grid of cells separated by walls on all sides, except for entrance and exit Then continually choose a wall randomly, and knock it down if the cells are not already connected to each other. If we repeat the process until the starting and ending cells are connected, we have a maze. It is better to continue knocking down the walls until every cell is reachable from every cell as this would generate more false leads in the maze. Test you algorithm by creating a 10 x 10 grid, and print all the walls that have been knocked down. the resulting maze (hand-drawing is acceptable)

Explanation / Answer

package doubleLinked;

/** Node of a doubly linked list of strings */
public class DNode {
   private String element; // String element stored by a node
   private DNode next, prev; // Pointers to next and previous nodes

   public DNode(String e, DNode p, DNode n) {
       element = e;
       prev = p;
       next = n;
   }

   public String getElement() {
       return element;
   }

   public DNode getPrev() {
       return prev;
   }

   public DNode getNext() {
       return next;
   }

   public void setElement(String newElem) {
       element = newElem;
   }

   public void setPrev(DNode newPrev) {
       prev = newPrev;
   }

   public void setNext(DNode newNext) {
       next = newNext;
   }
}

package doubleLinked;

/** Doubly linked list with nodes of type DNode storing strings. */
public class DList {
   private int size; // number of elements
   private DNode header, trailer; // sentinels

   /** Constructor that creates an empty list */
   public DList() {
       size = 0;
       header = new DNode(null, null, null); // create header
       trailer = new DNode(null, header, null); // create trailer
       header.setNext(trailer); // make header and trailer point to each other
   }

   /** Returns the number of elements in the list */
   public int size() {
       return size;
   }

   /** Returns whether the list is empty */
   public boolean isEmpty() {
       return (size == 0);
   }

   public DNode getFirst() throws IllegalStateException {
       if (isEmpty())
           throw new IllegalStateException("List is empty");
       return header.getNext();
   }

   public DNode getLast() throws IllegalStateException {
       if (isEmpty())
           throw new IllegalStateException("List is empty");
       return trailer.getPrev();
   }

   public DNode getPrev(DNode v) throws IllegalArgumentException {
       if (v == header)
           throw new IllegalArgumentException("Cannot move back past the header of the list");
       return v.getPrev();
   }

   public DNode getNext(DNode v) throws IllegalArgumentException {
       if (v == trailer)
           throw new IllegalArgumentException("Cannot move forward past the trailer of the list");
       return v.getNext();
   }

   public void addBefore(DNode v, DNode z) throws IllegalArgumentException {
       DNode u = getPrev(v); // may throw an IllegalArgumentException

       z.setPrev(u);
       z.setNext(v);
       v.setPrev(z);
       u.setNext(z);
       size++;
   }

   public void addAfter(DNode v, DNode z) throws IllegalArgumentException {
       DNode w = getNext(v); // may throw an IllegalArgumentException

       z.setPrev(v);
       z.setNext(w);
       w.setPrev(z);
       v.setNext(z);
       size++;
   }

   public void addFirst(DNode v) {
       addAfter(header, v);
   }

   public void addLast(DNode v) {
       addBefore(trailer, v);
   }

   public void removeFirst() {

       header = header.getNext();
       header.getPrev().setNext(null);
       header.getPrev().setPrev(null);
       header.setPrev(null);
       size--;
   }

   public void removeLast() {

       trailer = trailer.getPrev();
       trailer.getNext().setNext(null);
       trailer.getNext().setPrev(null);
       trailer.setNext(null);
       size--;
   }

   public void remove(DNode v) {
       DNode u = getPrev(v); // may throw an IllegalArgumentException

       DNode w = getNext(v); // may throw an IllegalArgumentException
       // unlink the node from the list
       w.setPrev(u);
       u.setNext(w);
       v.setPrev(null);
       v.setNext(null);
       size--;
   }

   public void moveToFirst(DNode v) {
       remove(v);
       addFirst(v);
   }

   public void moveToLast(DNode v) {
       remove(v);
       addLast(v);
   }

   public boolean hasPrev(DNode v) {
       return (v.getPrev() != header) && (v != header);
   }

   public boolean hasNext(DNode v) {
       return (v.getNext() != trailer) && (v != trailer);
   }

   /** Returns a string representation of the list */
   public String toString() {
       String s = "[";
       DNode v = header.getNext();
       while (v != trailer) {
           s += v.getElement();
           v = v.getNext();
           if (v != trailer)
               s += ",";
       }
       s += "]";
       return s;
   }

   public static void main(String[] args) {
       DList list = new DList();
       list.operate(list);
   }

   private void operate(DList list) {

       DNode a = new DNode("a", null, null);
       DNode b = new DNode("b", null, null);
       DNode c = new DNode("c", null, null);
       DNode d = new DNode("d", null, null);
       DNode e = new DNode("e", null, null);
       DNode x = new DNode("x", null, null);
       DNode y = new DNode("y", null, null);

       list.addLast(a);
       list.addLast(b);
       list.addLast(c);
       list.addLast(d);
       list.addLast(e);
       System.out.print("Adding a,b,c,d,e: ");
       System.out.println(list.toString());

       System.out.print("Adding x to first: ");
       list.addFirst(x);
       System.out.println(list.toString());

       System.out.print("Adding y to last: ");
       list.addAfter(e, y);
       System.out.println(list.toString());

       System.out.print("remove c: ");
       list.remove(c);
       System.out.println(list.toString());

       System.out.print("Remove first: ");
       list.removeFirst();
       System.out.println(list.toString());

       System.out.print("Remove last:");
       list.removeLast();
       System.out.println(list.toString());

       System.out.print("Bring d to first: ");
       list.moveToFirst(d);
       System.out.println(list.toString());

       System.out.print("Bring b to last: ");
       list.moveToLast(b);
       System.out.println(list.toString());
   }
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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