Setup

We want to write a program to identify palindromes.

Create a project in your favorite IDE (i.e., Eclipse or NetBeans), and import the source file Lab16_Main.java

import java.io.*; import java.util.*; public class CPS151_Lab16 { /** * isPalindrome(String) -> boolean * * @param input the given String * @return true/false based on whether or not the given String is a palindrome */ private static boolean isPalindrome(String input) { // 1. declare/create a Stack of Characters *** ADD CODE HERE *** // 2. declare a Queue of Characters; create it as a LinkedList of Characters // *** ADD CODE HERE *** // 3. for each character in the input String: // if the character c is a letter: // push the lower-case version of c onto the stack // add the lower-case version of c onto the queue // // HINTS: the static boolean method Character.isLetter(c) returns true/false // based on whether the character c is a letter // the static char method Character.toLowerCase(c) returns the given // character c as a lower-case letter // // *** ADD CODE HERE *** // 4. as long as neither the stack nor queue is empty: // pop the next character c1 off the stack // remove the next character c2 off the queue // if c1 != c2: // return false // // *** ADD CODE HERE *** return true; } // end isPalindrome /* * DO NOT MODIFY THIS CODE IN ANY WAY! * * 1. get String as user input * 2. determine if String is a palindrome by * passing it to the isPalindrome method * 3. tell user if it is or not */ public static void main(String[] args) { cout.print("Enter a word or phrase: "); String input = cin.nextLine(); if (isPalindrome(input)) { cout.printf("\"%s\" is a palindrome ", input); } else { cout.printf("\"%s\" is not a palindrome ", input); } } // end main 

Palindromes (from Wikipedia)

Palindromes date back at least to 79 AD, as a palindrome was found as a graffito at Herculaneum, a city buried by ash in that year. This palindrome, called the Sator Square, consists of a sentence written in Latin: "Sator Arepo Tenet Opera Rotas" ("The sower Arepo holds with effort the wheels"). It is remarkable for the fact that the first letters of each word form the first word, the second letters form the second word, and so forth. Hence, it can be arranged into a word square that reads in four different ways: horizontally or vertically from either top left to bottom right or bottom right to top left. As such, they can be referred to as palindromatic. The palindromic Latin riddle "In girum imus nocte et consumimur igni" ("we go wandering at night and are consumed by fire") describes the behavior of moths. It is likely that this palindrome is from medieval rather than ancient times. Byzantine Greeks often inscribed the palindrome, "Wash [the] sins, not only [the] face" ("Nipson anommata m monan opsin", engraving "ps" with the single Greek letter , psi), on baptismal fonts. This practice was continued in many English churches. Examples include the font at St. Mary's Church, Nottingham and also the font in the basilica of St. Sophia, Constantinople, the font of St. Stephen d'Egres, Paris; at St. Menin's Abbey, Orlans; at Dulwich College; and at the following churches: Worlingworth (Suffolk), Harlow (Essex), Knapton (Norfolk), St Martin, Ludgate (London), and Hadleigh (Suffolk). A palindrome with the same square property is the Hebrew palindrome, "We explained the glutton who is in the honey was burned and incinerated", ( ; perashnu: ra`avtan shebad'vash nitba`er venisraf), credited to Abraham ibn Ezra in 1924,[1] and referring to the halachic question as to whether a fly landing in honey makes the honey treif (non-kosher).

Famous palindromes

Some well-known English palindromes are, "Able was I ere I saw Elba", "A man, a plan, a canal - Panama", "Madam, I'm Adam" and "Never odd or even". English palindromes of notable length include mathematician Peter Hilton's "Doc, note: I dissent. A fast never prevents a fatness. I diet on cod" and Scottish poet Alastair Reid's "T. Eliot, top bard, notes putrid tang emanating, is sad; I'd assign it a name: gnat dirt upset on drab pot toilet."

Complete the Palindrome Program

Use a stack and a queue to complete the code in Lab16_Main.java (isPalindrome method) as follows:

Declare and create a stack of characters (Stack).

Declare a queue of characters (Queue), and create it as a linked list of characters (LinkedList).

For each character c in the input String: if c is a letter1:

push the lower-case version2 of c onto the stack

add the lower-case version of c onto the queue

otherwise, ignore c (do nothing)

As long as the stack is not empty and the queue is not empty:

pop the next character c1 off the stack

remove the next character c2 off the queue

if c1 != c2: return false

return true

Notes

The static boolean method Character.isLetter(c) returns true/false based on whether the character c is a letter.

The static char method Character.toLowerCase(c) returns the given character c as a lower-case letter.

Test Palindromes

Test as many of the palindromes at http://www.palindromelist.net as you can to make sure your program works; there are sure many to choose from!