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.

 
Powered by