Fluent Essays

Hello, Exercice 1 In this exercise, we will compare 2 classes used to create stacks: ArrayStack and NodeStack. The necessary files are in the ex1 folder. 2 files are provided to be able to compare these classes: tryStack1.java and tryStack2.java. To do: 1. Compile and run tryStack1 2. Compile and run tryStack2 3. Based on the results obtained and the code provided, answer the following questions : • What can we say about the execution of tryStack1 and tryStack2? • Describe the flow of the call to tryStack1 and tryStack2. • What are the implementation differences between tryStack1 and tryStack2? • What did we want to highlight? Exercise 2: Implementing doubly linked lists In this exercise, we will implement a class to create and manage doubly lists chained. The necessary files are in the ex2 folder. The code for doubly linked lists is in the DLinkedList.java file. However, 2 functions have not been implemented: InsertNode (ListNode nNode, ListNode pAfter) and RemoveNode (ListNode nNode). The objective of this exercise is to implement the 2 missing methods. To do: 1. Implement the InsertNode (ListNode nNode, ListNode pAfter) method. This method inserts the nNode node after the pAfter node in the current list. 2. Implement the RemoveNode (ListNode nNode) method. This method removes the nNode node from the current list. 3. Compile and run the TestDLinkedList.java file to validate your implementation. Exercise 3: Using batteries In this exercise, we will use a stack to verify the correspondence of opening and closing parentheses in an expression. The necessary files are in the ex3 folder. The code to implement is in the bracketsBalance.java file. However, 1 function does not have been implemented: boolean bBalance (String exp). The objective of this exercise is to implement the missing method. Steps to follow 1. Implement the boolean bBalance (String exp) method. • This method evaluates the expression exp for matching parentheses. It returns true if the parentheses are well organized, false otherwise. • Use the stack implementation in ArrayStack.java to help you. 2. Compile the bracketsBalance.java file. Test it with different expressions in order to validate your implementation. ex1/tryStack2.java ex1/tryStack2.java class  tryStack2  {      public   static   void  main (   String   []  args  )   {          Integer   []     arr  =   new   Integer   [   50   ];          for (   int  i  =   0 ;  i  <   50 ;  i ++   )   {             arr  [  i  ]   =   new   Integer   (  i  *   2   );          }         printA  (  arr  );         arr  =  reverse  (  arr  );         printA  (  arr  );      }   /* main */      public   static   Integer   []  reverse (   Integer   []  a  )   {          NodeStack     S  =   new   NodeStack ();          Integer   []     b  =   new   Integer   [  a . length  ];          for (   int  i  =   0 ;  i  <  a . length ;  i ++   )   {             S . push  (  a  [  i  ]   );          }          for (   int  i  =   0 ;  i  <  a . length ;  i ++   )   {             b  [  i  ]   =   ( Integer )   ( S . pop ()   );          }          return  b ;      }   /* reverse */      public   static   void  printA (   Integer   []  a  )   {          System . out . println ();          for (   int  i  =   0 ;  i  <   50 ;  i ++   )   {              System . out . print  (  a  [  i  ]. intValue ()   +   \t   );          }          System . out . println ();      }   /* printA */ } ex1/tryStack1.java ex1/tryStack1.java class  tryStack1  {      public   static   void  main (   String   []  args  )   {          Integer   []     arr  =   new   Integer   [   50   ];          for (   int  i  =   0 ;  i  <   50 ;  i ++   )   {             arr  [  i  ]   =   new   Integer   (  i  *   2   );          }         printA  (  arr  );         arr  =  reverse  (  arr  );         printA  (  arr  );      }   /* main */      public   static   Integer   []  reverse (   Integer   []  a  )   {          ArrayStack     S  =   new   ArrayStack   (  a . length  );          Integer   []     b  =   new   Integer   [  a . length  ];          for (   int  i  =   0 ;  i  <  a . length ;  i ++   )   {             S . push  (  a  [  i  ]   );          }          for (   int  i  =   0 ;  i  <  a . length ;  i ++   )   {             b  [  i  ]   =   ( Integer )   ( S . pop ()   );          }          return  b ;      }   /* reverse */      public   static   void  printA (   Integer   []  a  )   {          System . out . println ();          for (   int  i  =   0 ;  i  <   50 ;  i ++   )   {              System . out . print  (  a  [  i  ]. intValue ()   +   \t   );          }          System . out . println ();      }   /* printA */ } ex1/Stack.java ex1/Stack.java /**  * Interface for a stack: a collection of objects that are inserted  * and removed according to the last-in first-out principle.  *  *  @author  Roberto Tamassia  *  @author  Michael Goodrich  *  @see  EmptyStackException  */ public   interface   Stack   {      /**      * Return the number of elements in the stack.      *  @return  number of elements in the stack.      */      public   int  size ();      /**      * Return whether the stack is empty.      *  @return  true if the stack is empty, false otherwise.      */      public   boolean  isEmpty ();      /**      * Inspect the element at the top of the stack.      *  @return  top element in the stack.      *  @exception  EmptyStackException if the stack is empty.      */      public   Object  top ()      throws   EmptyStackException ;      /**      * Insert an element at the top of the stack.      *  @param  element element to be inserted.      */      public   void  push (   Object  element  );      /**      * Remove the top element from the stack.      *  @return  element removed.      *  @exception  EmptyStackException if the stack is empty.      */      public   Object  pop ()      throws   EmptyStackException ; } ex1/NodeStack.java ex1/NodeStack.java /**  * Implementation of Stack interface, based on Node class (dynamic).  */ public   class   NodeStack   implements   Stack   {      // reference to the head node      protected   Node  top ;      // number of elements in the stack      protected   int  size ;      /**      * Constructor fo NodeStack class.      *  @return  an empty stack      */      public   NodeStack ()   {         top   =   null ;         size  =   0 ;      }      public   int  size ()   {          return  size ;      }   /* size */      public   boolean  isEmpty ()   {          if (  top  ==   null   )              return   true ;          return   false ;      }   /* isEmpty */      public   Object  top ()   throws   EmptyStackException   {          if (  isEmpty ()   )              throw   new   EmptyStackException   (   Stack is empty.   );          return  top . getElement ();      }   /* top */      public   void  push (   Object  elem  )   {          // create and link-in a new node          Node     v  =   new   Node   (  elem ,  top  );         top  =  v ;         size ++ ;      }   /* push */      public   Object  pop ()   throws   EmptyStackException   {          if (  isEmpty ()   )              throw   new   EmptyStackException   (   Stack is empty.   );          Object     temp  =  top . getElement ();          // link-out the former top node         top  =  top . getNext ();         size -- ;          return  temp ;      }   /* pop */ } ex1/Node.java ex1/Node.java /**  * Node used for chained data structures.  * This class is used to create a single element in such chains (simple chained).  */ public   class   Node   {      // Element in the node.      private   Object  element ;      // Next element after this node.      private   Node  next ;      /**      * Node class constructor without parameters.      *  @return  a node with null reference to its element and next node.      */      public   Node ()   {          this ( null ,   null );      }      /**      * Node class constructor given an object and next node.      *  @param   Object e             element to store in the node      *  @param   Node   n             next node      *  @return         created node with element e and next node n      */      public   Node (   Object  e ,   Node  n  )   {         element  =  e ;         next     =  n ;      }      /** Getters */      public   Object  getElement ()   {          return  element ;      }   /* getElement */      public   Node  getNext ()   {          return  next ;      }   /* getNext */      /** Setters */      public   void  setElement (   Object  newElem  )   {         element  =  newElem ;      }   /* setElement */      public   void  setNext (   Node  newNext  )   {         next  =  newNext ;      }   /* setNext */ } ex1/FullStackException.java ex1/FullStackException.java /**  * Runtime exception thrown when one tries to perform operation push  * on a full stack.  */ public   class   FullStackException   extends   RuntimeException   {      public   FullStackException (   String  err  )   {          super ( err );      } } ex1/EmptyStackException.java ex1/EmptyStackException.java /**  * Runtime exception thrown when one tries to perform operation top or  * pop on an empty stack.  */ public   class   EmptyStackException   extends   RuntimeException   {      public   EmptyStackException (   String  err  )   {          super ( err );      } } ex1/ArrayStack.java ex1/ArrayStack.java /**  * Implementation of the Stack interface using a fixed-length array.  * An exception is thrown if a push operation is attempted when the  * size of the stack is equal to the length of the array.  *  *  @author  Natasha Gelfand  *  @author  Roberto Tamassia  *  @see  FullStackException  */ public   class   ArrayStack   implements   Stack   {      // Default length of the array used to implement the stack.      public   static   final   int  CAPACITY  =   1000 ;      // Length of the array used to implement the stack.      protected   int  capacity ;      // Array used to implement the stack.      protected   Object  S  [];      // Index of the top element of the stack in the array.      protected   int  top  =   - 1 ;      /**      * ArrayStack class constructor, with no parameter.      * Default length used for the array is CAPACITY.      */      public   ArrayStack ()   {          this ( CAPACITY );      }      /**      * ArrayStack class constructor.      *  @param  cap length of the array.      */      public   ArrayStack (   int  cap  )   {         capacity  =  cap ;         S         =   new   Object   [  capacity  ];      }      public   int  size ()   {          return   ( top  +   1 );      }   /* size */      public   boolean  isEmpty ()   {          return   ( top  <   0 );      }   /* isEmpty */      public   Object  top ()   throws   EmptyStackException   {          if (  isEmpty ()   )              throw   new   EmptyStackException   (   Stack is empty.   );          return  S  [  top  ];      }   /* top */      /**      * Be careful here, this implementation may throw an exception.      *  @exception  FullStackException if the array is full.      */      public   void  push (   Object  obj  )   throws   FullStackException   {          if (  size ()   ==  capacity  )              throw   new   FullStackException   (   Stack overflow.   );         S  [   ++ top  ]   =  obj ;      }   /* push */      public   Object  pop ()   throws   EmptyStackException   {          if (  isEmpty ()   )              throw   new   EmptyStackException   (   Stack is Empty.   );          Object     elem  =  S  [  top  ];          // dereference S[top] for garbage collection.         S  [  top --   ]   =   null ;          return  elem ;      }   /* pop */ } ex2/TestDLinkedList.java ex2/TestDLinkedList.java /**  *  Class to test doubly linked list  *   @author  Jeff Souza  */ class   TestDLinkedList   {      public   static   void  main (   String   []  args  )   {          // Create a new node, with data = 1          ListNode     nNode  =   new   ListNode ();         nNode . data  =   1 ;          // Create a new doubl- linked list with the node          DLinkedList     list  =   new   DLinkedList ();         list . firstNode  =  nNode ;         list . lastNode   =  nNode ;          // Add items to linked list (2, 3, 4, 5, 6, 7 , 8, 9 and 10)          for (   int  i  =   2 ;  i  <   11 ;  i ++   )   {             nNode       =   new   ListNode ();             nNode . data  =  i ;             list . AppendNode   (  nNode  );          }          // Print the content of the list          System . out . println ();         list . print ();          // Remove items from linked list (2 first elements and the last one)          System . out . println  (   items removed.   );         list . RemoveNode   (  list . firstNode  );         list . RemoveNode   (  list . firstNode  );         list . RemoveNode   (  list . lastNode  );          // Print the content of the list         list . print ();      }   /* main */ } ex2/ListNode.java ex2/ListNode.java /**  *  Class node of a doubly linked list.  *   @author  Jeff Souza  */ class   ListNode   {      // Node data      int  data ;      // Next node      ListNode  next ;      // Previous node      ListNode  previous ; } ex2/DLinkedList.java ex2/DLinkedList.java /**  *  Class doubly linked list.  *   @author  Jeff Souza  */ class   DLinkedList   {      // First node of the list.      ListNode  firstNode ;      // Last node of the list.      ListNode  lastNode ;      /**      * Appends a node to the end of the list.      *  @param  ListNode nNode Node to append.      */      void   AppendNode (   ListNode  nNode  )   {          InsertNode   (  nNode ,  lastNode  );      }   /* AppendNode */      /**      * Inserts a node into the list after pAfter node.      *  @param  ListNode nNode  Node to insert.      *  @param  ListNode pAfter Node after which the insertion is done.      */      void   InsertNode (   ListNode  nNode ,   ListNode  pAfter  )   {          // INSERT YOUR CODE HERE      }   /* InsertNode */      /**      * Removes the specified node from the list.      *  @param  ListNode nNode Node to remove.      */      void   RemoveNode (   ListNode  nNode  )   {          // INSERT YOUR CODE HERE      }   /* RemoveNode */      /**      * Prints the content of the list.      */      void  print ()   {          ListNode     nNode  =   null ;          System . out . print  (   Current list:    );          for (  nNode  =  firstNode ;  nNode  !=   null ;  nNode  =  nNode . next  )   {              System . out . print  (  nNode . data  +       );          }          System . out . println  (     );      }   /* print */ } ex3/FullStackException.java ex3/FullStackException.java /**  * Runtime exception thrown when one tries to perform operation push  * on a full stack.  */ public   class   …