## 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.
• StackIntf.java
• ArrayStackHW5.java
• File2String.java
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
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:
• 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.
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:
• if the character is a 1, UNDO the previous character (that is, remove the last character that was added to the stack).
(if there is nothing to undo, do nothing)
• else if the character is a 9
print the contents of the stack by popping each item then exit
• else if the character is an upper or lower case letter add it to the stack
To see if a letter is a lower case letter you can use the following code snippet as a guide
```		String ss = "The quick BrowN foX JUMPS";
for (int i = 0; i < ss.length(); i++) {
char c = ss.charAt(i);
if (c >= 'a' && c <= 'z') {
System.out.println("LOWER: " + c);
}
}
```
• else if the character is an underscore ‘_’ (ASCII value 95), add it to the stack
we use _ instead of space because I can see _ and I can’t see ‘ ‘.
• else ignore all other characters.
• if you run out of characters in a line before getting a ‘9’, read another 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: