This assignment follows up on several informal exercises suggested in lecture, so you should have most of this done already. The assignment is partly an exercise in implementation (which should be straightforward) and partly one in design (which may be both a bit harder and more nebulous): the design part comes in specifically in the interface for the linked lists, where you must make some decisions on what is reasonable to include (and to implement).
Write up the following interfaces and classes for linked lists in Java (some were given in lecture, but make sure you have your own copies, to check that they all compile together):
Listy which includes operations for adding
(at the end), removing, finding size, etc., for lists, conceived generally;
SLListNode which implements a basic linked list node
with a single item (of type Object) and a single (recursive) reference
to another node;
SinglyLinkedList which "wraps" a reference to a singly-linked
list node, and which implements the Listy interface from above.
CircLinkedList which "wraps" a reference to a singly-linked
list node, and which implements the Listy interface from above,
but this time using a circularly-linked list (i.e., the last node points back at the
first one, rather than referring to null).
Be ready to defend decisions you made concerning what operations you included in the interface, and any challenges you encountered in implementing the interface for the two different classes.
Write up the following interfaces and classes for stacks in Java, along with one project implementation (the bracket checker); you may use either implementation to test your project.
Stack which includes operations for pushing,
popping, checking for empty and full-to-capacity, and size (you should have
this all written down from the guest lecture on Friday the 13th);
ArrayStack which implements the Stack
interface using arrays ((again, you should have this in your notes from lecture);
ListStack which implements the Stack interface
using a linked list; this will be an "adapter" that provides the Stack
operations in terms of what a list provides.
Finally, you should provide a short little project which checks for balanced brackets in a string, using a stack. The idea is that an input string (read in via GUI or command line) will contain a mixture of parentheses (round: "()"), brackets (square: "[]") and braces (curly: "{}"), and that your program should either validate that it contains only well-nested, well-sequenced pairs, or indicate what sort of error happens. (Let's allow spaces, too, just to make it easier to write the examples: just ignore the spaces.)
For example, on input "( ()[] { [] () } )" your program would respond that the
brackets (in the general sense) are all balanced properly.
But on input "( [ ] { ( } ) )" you would report a mis-match at the first closing
(curly) brace, since it does not match the preceding open parenthesis.
(How do you implement this? Simple! Just use a stack! Push every "left" bracket and make sure you can pop (off the top of the stack) a corresponding "right" one, i.e., of the corresponding "shape". You should always find a match, never see an empty stack, when matching, and end up with an empty stack at the end. (Why?)