How can I remove an element in a repeated list?

Programming with Dynamic Data Structures

• 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

• Answer:

  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