CS 206 - Introduction to Data Structures

Using Stacks

Due

There are three parts to this homework. In the first part you will complete a partial implementation of an array-based stack. In the second and third parts you will use that stack to find palindromes and simulate the UNDO function of a text editor.
 
Create a new folder, presumably named Assignment5, and copy the following code into it. All of the code is available on powerpuff in the directory /home/gtowell/Public/206/a5/. Use cp or scp as needed to copy this code to the directory containing the work for this assignment.

Complete ArrayStack

Two functions (push and pop) in ArrayStackHW5.java need to be implemented. Do that.

Find Palindromes

A classic use of Stacks is to determine if a given string is a palindrome. In this part of the assignment you will use stacks to determine if a text contains a palindrome. In particular, you will check if a text file contains palindromes of lengths 2-50.

If the text does contain a palindrome of a particular length, print out the starting position of the palindrome in the text and the palindrome. If the text contains more than one palindrome of a given length, the program should only show the location and text of the first palindrome. For example, given the text:
aaronbobadammadrigalagnew
Your program should return
2 0 aa
3 5 bob
4 10 amma
5 17 galag
6 9 dammad
7  
. . .
Per common palindrome rules you should make everything lower case and ignore everything other than a-z when determining palindromeness (assuming that is a word). You may assume that File2String has done this work; any characters remaining in the string received from that class must be used.

Requirements: Suggestion for approaching the problem:
  1. Make a small testing file for yourself. This should have a palindromes of known sizes at known locations. Use this file (and update it as needed) during development. The file need not be real words. For instance, "abcbaabcccb" might be a good starting point, although this is arguably too complex. It has a lot of palindromes. Before you start, you should know exactly the location of every palindrome in your test file.
  2. Draw pictures / write text that states clearly what data is moving where. A step-by-step picture of the content of all variables (data structres) is not unwarranted. Think of cartoon-like panels. If you get these pictures/text doe at least 48 hours prior to the assignment due date, and you you like me to comment, send me email; I will review and comment within 12 hours. For instance, draw pictures for just the next suggested step below.
  3. Start by just determining if a palindrome of a given size (say 5) exists starting at the first character in the string. Write a function like boolean pal5st0(String s) which returns true if a palindrome of length 5 exists in the string s and which starts at position 0 in the string.
  4. Only when you have that function working, consider extending that function so it could find a palindrome of length 5 at a given position in the text. (Hint, add another parameter to hold the position to be checked). Add two or three instances of the use of your function to the program. Make sure that these instances are doign the right things.
  5. put the call to this method in a loop that checks evey possible starting position of a palindrome of length 5.
  6. Once you have that working, consider further extending you palindrome checker to handle other palindrome lengths.

Extra Credit: Simulating Undo in an editor

This is work up to 15 points of extra credit.
Extra credit is only available if the first two parts of the main assignment are competently executed

Editors use a stack for Undo. In this part of the assignment you will use the stack from part 1 to simulate typing with undo. Here is what you need to do:
Use scanner to read from the keyboard one line at a time. Then with each character in the line: So for instance, given
input: 
    asdf_ghij1111jj8765439
output: 
    jj_fdsa

input: 
    qwert_yuio_hhh
    1111abc19wwwww
output:
    baoiuy_trewq
The charAt function of String will be useful for this part.

Suggested approach

  1. Add every letter regardless of anything to the stack. The only character handled specially should be the '9'. On receiving a '9', pop everything off the stack and print one character at a time. (Doing this, in good style with appropriate comments, is worth about 85% of this part of the assignment.)
  2. handle the '1' character
  3. Allow only characters and '-' to be added to the stack.

What to Turn In

  1. All code your wrote or edited, well commented
  2. README with the usual information.
  3. A text file you made up to test your palindrome finder. I will have my own for testing, but you should have one too.

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items:

The following steps for submission assume that you created a project named AssignmentN in the directory /home/YOU/cs206/

  1. For this assignment N=5
  2. Put the README file into the project directory
  3. Go to the directory /home/YOU/cs206
  4. Enter /home/gtowell/bin/submit -c 206 -p N -d AssignmentN

For more on using the submit script click here