Computer Science 230 Assignment 2

Objectives:
to improve the generic stack ADT in Java
to use a stack to solve a (small) real-life problem
Assignment – Part 1: Download the author's interface GenericNode, and classes GenericStack, ListingGS, and MainGenericStack, from WebCT. In GenericStack incrementally implement the following methods: reset(), to set the stack back to empty; isEmpty(), to test whether the stack is empty; isFull(), to test whether the stack is full; peek(), to return the top value in the stack without removing it from the stack. Add code to MainGenericStack to test the new methods incrementally. Assignment – Part 2: Write a Java class, CharacterGS, that implements the interface GenericNode. The only field in this class is a char. You will need a constructor and a getter to put the char in and get it back out. The interface will force you to write a deepCopy() and a toString(), but you won't need those. Write a Java class, Balanced, that uses a Stack to solve the following problem. Within Balanced declare a GenericStack. Within a main() method, read from a text file, data.txt. Output is to the monitor. You must not use anything other than the stack to solve the problem. In particular you must not use any counters, and you must not scan the input String from both directions. Scan the input String in a single left-to-right pass. Each line of the input file will consist of square brackets and parentheses. Read each line, echo it to the monitor, determined whether it is balanced by the rules below, and display "Balanced" or "Not Balanced" (as the case may be) on the monitor. Rules for determining balance: a sequence of parentheses and brackets is balanced if it meets any of the following criteria: 1. A right parenthesis balances a single preceding left parenthesis. For example, (), (()), and ()() are all balanced. 2. If no unbalanced preceding left bracket exists, a right bracket balances all preceding left parentheses. For example, ( ], ((( ], and ( ](( ] are all balanced. 3. If an unbalanced preceding left bracket exists, a right bracket balances the left bracket and all left parentheses that follow the left bracket and precede the right bracket. For example, [((( ], and [[(( ]] are all balanced. A sequence is unbalanced if any left parenthesis or bracket remains unbalanced by a right parenthesis or bracket, if a right parenthesis or bracket begins a sequence or immediately follows a balanced sequence, or if a right parenthesis immediately follows an unbalanced left bracket. For example, (( ), )(), ()(, ()), and [) are all unbalanced. Submission: Put your name in all files that you write. In the files written by the author of the text, indicate "modified by <your name". Submit the files GenericNode.java, GenericStack.java, CharacterGS.java, and Balanced.java on WebCT by the date and time specified above. No submissions will be accepted other than by WebCT.