CS 206 - Introduction to Data Structures
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.
Two functions (push and pop) in ArrayStackHW5.java need to be implemented. Do that.
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:
Your program should return
2 0 aa
3 5 bob
4 10 amma
5 17 galag
6 9 dammad
. . .
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.
Suggestion for approaching the problem:
- Your program must use the ArrayStack class you completed in Part 1.
- Your program must accept the name of a text file to check from the command line
- Your program must use File2String (from /home/gtowell/Public/206/a5/File2String.java)
- Your program must handle appropriately the exceptions thrown by File2String.
- Your program must check for all palindromes of length 1 - 50
- If a palindrome of a given length exists, show its starting location in the original text and the palindrome itself.
- If more than one palindrome of a given length exists in the text, show only the first.
- The text file to check for palindromeness must be supplied as a command line argument to your program.
- 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.
- 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.
- 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.
- 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.
- put the call to this method in a loop that checks evey possible starting position of a palindrome of length 5.
- 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
The charAt function of String will be useful for this part.
- 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.)
- handle the '1' character
- Allow only characters and '-' to be added to the stack.
What to Turn In
- All code your wrote or edited, well commented
- README with the usual information.
- A text file you made up to test your palindrome finder. I will have my own for testing, but you should have one too.
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:
- README: This file should follow the format of this sample README (https://cs.brynmawr.edu/cs206/README.txt)
- Within the README file, include a brief (max 1 paragraph) reflection on what went well and/or poorly and why
- Also within Readme, include a comparison of the times required for the task by your hashtable and ArrayList implementations. Also, some analysis of these times would be good.
- Source files: Every .java file used in the final version of every part of your project (including the imported files)
- Unique Data files used: If any
The following steps for submission assume that you created a project named AssignmentN in the directory /home/YOU/cs206/
- For this assignment N=5
- Put the README file into the project directory
- Go to the directory /home/YOU/cs206
- Enter /home/gtowell/bin/submit -c 206 -p N -d AssignmentN
For more on using the submit script click here