Description:
Programming using stacks and queues. Using stacks, write a program
that solve a problem. Using queues, add a new method to extend the
functionality of the queue program below. Write appropriate code to
test programs.

Procedure:
Sketch an algorithm to determine if a string is properly
parenthesized. For example, (), and (()()((())())) are properly
parenthesized, but (()))()(() and (() are not. Your algorithm must use
a stack.
Adapt code to manage stack of characters. 
Implement your algorithm to see if a string is properly parenthesized.
It should return true if it is and false if it is not.
 
Add a new method for the Class Queue below named "nth" which returns
the n'th item in the queue without disturbing the queue. Assume that
the front of the queue is the first item.
Write appropriate supporting code to test the method. 

// Queue.java
// A class that represents a queue implemented as a linked list.

public class Queue {

     // Inner class ListNode

        private class ListNode {

           // Data field
           private Object info;         //data stored in the node
           private ListNode link;       // link ot next node

           // Methods
           // Constructions
           // postcondition: Creates a new empty node.
           public ListNode() {
              info = null;
              link = null;
           }

           // postcondition: Creates a new node storing obj.
           public ListNode(Object obj) {
              info = obj;
              link = null;
           }

           // postcondition: Creates a new node storing obj
           //  and linked to node referenced by next.
           public ListNode(Object obj, ListNode next) {
              info = obj;
              link = next;
           }
       }
    
    // Data Fields
    private ListNode front;              // Reference to front of
queue
    private ListNode rear;               // Reference to front of
queue
    private int size;                    // Size of queue

    // Methods
    // postcondition: Inserts items in a new node and resets
    // rear to reference the new node. 
    // if this queue has 1 element, front references
    // the new node also.
    public void insert(Object item) {
       if (isEmpty()) { // Empty queue
           // Link rear and front to only node.
           rear = new ListNode(item);
           front = rear;
       }
       else { // extend a nonempty queue
            rear.link = new ListNode(item);
            rear = rear.link; // Move rear to new node
      }

     size++;      // Increment queue size.
   }

     // postcondition: If this queue is not empty, returns its
     // first element & front references new first element.
   public Object remove() {
        Object item = peek();       // Retrieve first item.

        // Remove first element.
        front = front.link;         // Delete first node.
        size--;                     // Decrement queue size.

        return item;
     }

     // precondition: The queue has been created.
     // postcondition: If this queue is not empty, returns its
     // first element; otherwise, throws an exception.
   public Object peek() {
       if (isEmpty())
             throw new NullPointerException();
       return front.info;
     }

    // postcondition: Returns true if this queue is empty; otherwise,
    //        return false.
   public boolean isEmpty() {
        return (size == 0);
     }

    // postcondition: Returns to the size of this queue.
    public int getSize() {
       return size;
    }
   public String toString() {
      String result = "";
      ListNode next = front;      // Start at front
      while (next != null) {
         result = result + next.info + "\n";
         next = next.link;
      }
      return resul;
   }
} // End of class queue



// QueueTest.java
// Test class queue

public class QueueTest {

    public static void main (String[] args) {
       Queue q = new Queue();
       String name;

   // Insert 4 names
   q.insert("Robert");
   q.insert("Bettina");
   q.insert("Maria");
   q.insert("Sergio");
   System.out.println(q.toString());

   name = (String) q.remove();
   System.out.println("Removed" + name);   // Displays Robert.
   q.insert("Lawson");
   System.out.println ("Inserted Lawson");

   name = (String) q.remove();
   System.out.println("Removed" + name); // Displays Bettina

   System.out.println("size of q is " + q.getSize());
   System.out.println(q.toSize());
  }
} // End of class QueueTest

Hi math01-ga,
   Glad to have you back! This time, instead of posting the source
code for your answer here, I have provided links to the java source
files containing the code. All you have to do is download the file and
compile it. As usual, all code has been tested with JDK 1.4
   On to the answers:

+-------------------------------------------------+
Algorithm for Parenthesis Matching:
    - Parse the input string character by character, from left to
right
       - When we encounter a opening bracket "(", we push it into the
stack
       - When we encounter a closing bracket ")", we pop the a bracket
from the stack. As long as there exists a corresponding "(" in the
stack for every ")" we encounter, the string is properly parenthesised
else its mismatched.
    - If we have finished parsing the string, but the stack is still
not empty, then there is a mismatch.(Too many opening brackets)

=================================================

Please download the file indicated below to see an implementation of
the above Parentheses Matching algorithm in Java.
    - MatchingTest.java
      ( http://member.isavvix.com/theta_ga/MatchingTest.java )

From your question, it was not clear whether you were interested in
the implementation of the algorithm only, or both algoritm and a Stack
class. To save time, I have used Java's built in Stack class from the
package java.util. You can find the help documentation for this class
here:
     - java.util.Stack
       ( http://java.sun.com/j2se/1.4/docs/api/java/util/Stack.html )
If, perchance, you wanted an implementation a stack class also, just
ask for a clarification, and I will post the code for you here.

+-------------------------------------------------+

You can download the java files containing the code for the solution
to the Queues question from the locations linked below:
     - Queue.java
       ( http://member.isavvix.com/theta_ga/Queue.java )
     - QueueTest.java
       ( http://member.isavvix.com/theta_ga/QueueTest.java )

You can easily find the code I have added in the above files, as my
additions are preceeded by the following comment line:
            " // ***** NEW ADDITION ***** "

The code has ample comments, so it should be easily understandable.
However, if you have any confusion or doubts, please ask for a
clarification, and I will provide a more in depth explaination.

+-------------------------------------------------+

Hope this helps.
If you need any clarifications, just ask!

Regards,
Theta-ga
:-)

==================================
Google Search Terms Used:
     java util stack

---

Request for Answer Clarification by math01-ga on 26 Feb 2003 14:50 PST

Hi theta-ga,

I am a little confused but will follow up with additional questions if
I need to. However, I did not see were you added a method to the queue
class according to my question.

"Add a new method for the Class Queue below named "nth" which returns
the n'th item in the queue without disturbing the queue. Assume that
the front of the queue is the first item.
Write appropriate supporting code to test the method".

---

Request for Answer Clarification by math01-ga on 27 Feb 2003 06:06 PST

Hi theta-ga,

Ran the program (MatchingTest) and it is not doing what it supposed
to. According to my question, the program is to determine if a string
is properly parenthesized. For example (), (()()((())())) are properly
parenthesized. Can you please write approprite code or test program
yourself to see the out of program.

---

Clarification of Answer by theta-ga on 27 Feb 2003 07:33 PST

Hi math01-ga,
   The nth() method, as required by your question, is declared at the
very end of the file Queue.java. The supporting code to test the
method can be found at the end of the main() method in the file
QueueTest.java
   As for the MatchingTest program, I tested it again, and it works as
asked. Perhaps you could provide more detail about the problems you
are experiencing?
   The file (MatchingTest.java) contains two methods. They are:
     - main(): The main method asks the user to input a parenthesised
string. It then passes this input string to the method IsMatching(),
and then displays IsMatching()'s return value on the screen.
     - IsMatching(String): This method takes a parenthesised string as
its argument. It returns true if the string is properly parenthesised
and false if it is not. This is the method which implements the
algorithm that was outlined in my earlier answer.

 This is the output I got when I tested out MatchingTest:

    Enter the parenthesised string: (()()((())()))
    Algorithm returned true

  As you can see, this is exactly what the questioned asked
:"Implement your algorithm to see if a string is properly
parenthesized. It should return true if it is and false if it is not."

Hope this helps. 
If you have any other queries, just ask!

Happy Coding!
Theta-ga
:-)

---

Request for Answer Clarification by math01-ga on 28 Feb 2003 00:51 PST

Hi theta-ga,

When I compiled and ran the queue program, I kept getting errors. Can
you explain how you compiled and ran the program without erros? Are
there some changes that need to be made to the program?

Regards

---

Request for Answer Clarification by math01-ga on 28 Feb 2003 01:02 PST

Disregard my last request for answer clarification. Program works.

---

Clarification of Answer by theta-ga on 01 Mar 2003 09:32 PST

Glad to have been of help.
:-)