You are to implement a Palindrome detector JAVA program. A palindrome is a serie

Question

You are to implement a Palindrome detector JAVA program. A palindrome is a series of intelligible characters that read the same both forward and backwards, excluding punctuation and spaces and normalizing case. The basic algorithm for this program will be:

1. Remove all punctuation and spaces (work on a copy of the data, maintain the original).

2. Change all characters to a single case (either upper or lower).

3. Submit each character from the beginning of the string through the end of the string to both a stack and queue.

4. Remove each character from both the stack and queue, comparing the output as they are removed.

5. If the end of the stack and queue are reached and there are no mismatches, the string is a valid palindrome.

Legal Input will consist of a user entered sentence. Desired output will be whether or not the input sentence is a palindrome (yes, if it is, no, if it is not). An example of a valid palindrome is: "A man, a plan, a canal, Panama!" The letters amanaplanacanalpanama read the same both forward and backwards.

The output should include the original input, the printed output from the stack and queue, and lastly, the palindrome determination (yes or no).

Ensure you:

Create your own stack and queue class with appropriate (usual) member methods. You may adapt your linked list class to function as a queue. The stack will be implemented with an array. You can use built in methods to do case conversion or string manipulation but DO NOT USE built-in stack or queue classes.

Appropriately name your variables and methods

Think/plan/draw/design before you code; ensure you comment your logic

Make the program as modular as possible (you should have a minimum of 3 classes)

Provide error checking for the program.

Allow the user to enter more than one sentence (i.e. loop user attempts - again “menu”)

Explanation / Answer

Provided below are the classes needed. I have also written a LinkedList class. In case you have your own linked list implementation with all the methods that are in this answer's linked list implementation, then you can ignore the linked list given here. Otherwise please use all the classes. Output is shown at end. Hope the answer helps. If it did, please don't forget to rate the answer . Thank you very much.

LinkedList.java

public class LinkedList<T> {
class Node
{
T data;
Node next;
Node(T val, Node nxt)
{
data = val;
next = nxt;
}
}
private Node head, tail;
private int size;
public LinkedList()
{
head = null;
tail = null;
size = 0;
}
public boolean isEmpty()
{
return size == 0;
}
void add(T elem)
{
if(isEmpty())
head = tail = new Node(elem, null);
else
{
tail.next = new Node(elem, null);
tail = tail.next;
}
size++;
}
//removes and returns an element at specified index, null is returned if no such element
T remove(int index)
{
if(isEmpty() || index >= size() || index < 0)
return null;
else
{
Node prev = null, curr = head;
for(int i = 0; curr != null && i < index; i++)
{
prev = curr;
curr = curr.next;
}
if(curr == null)
return null;
else
{
if(curr == head) //removiing head node
head = head.next;
else
prev.next = curr.next;
if(curr == tail) //update if tail node was removed
tail = prev;
size--;
return curr.data;
}
}
}
public int size()
{
return size;
}
//get the element at index
public T get(int index)
{
if(isEmpty() || index >= size() || index < 0)
return null;
Node curr = head;
for(int i = 0; i < index; i++)
curr = curr.next;
return curr.data;
}
}

Stack.java

public class Stack<T> {
private LinkedList<T> list;
public Stack()
{
list = new LinkedList<T>();
}
public void push(T elem)
{
list.add(elem);
}
public T pop()
{
return list.remove(size() - 1); //remove the last eleemnet
}
public T peek()
{
return list.get(size() - 1); //get the last element
}
public int size()
{
return list.size();
}
public boolean isEmpty()
{
return list.isEmpty();
}
}

Queue.java

public class Queue<T> {
private LinkedList<T> list;
public Queue()
{
list = new LinkedList<T>();
}
public boolean isEmpty()
{
return list.isEmpty();
}
public void enque(T elem)
{
list.add(elem);
}
public T deque()
{
return list.remove(0); //remove the 1st element
}
public int size()
{
return list.size();
}
}

CheckPalindrome.java

import java.util.Scanner;
public class CheckPalindrome {
private static void check(String str)
{
String cleanedStr = "";
//remove non-alphabetic characters
for(int i = 0; i < str.length(); i++)
{
char ch = str.charAt(i);
if(Character.isAlphabetic(ch))
cleanedStr += ch;
}
cleanedStr = cleanedStr.toLowerCase(); //convert to lowercase
System.out.println("Input string: " + str);
System.out.println("Cleaned string: " + cleanedStr);
Stack<Character> stk = new Stack<Character>();
Queue<Character> que = new Queue<Character>();
//submit each character to both stack and queue
for(int i = 0; i < cleanedStr.length(); i++)
{
char ch = cleanedStr.charAt(i);
stk.push(ch);
que.enque(ch);
}
char ch1, ch2;
boolean valid = true;
while(!stk.isEmpty())
{
ch1 = stk.pop();
ch2 = que.deque();
System.out.println("Stack = " + ch1 + " Queue = " + ch2);
if(ch1 != ch2)
{
valid = false;
break;
}
}
if(valid)
System.out.println("Yes");
else
System.out.println("No");
}
public static void main(String[] args) {
Scanner keybd = new Scanner(System.in);
String line = "";
while(true)
{
System.out.println("Enter a line to check. Type quit to end the program.");
line = keybd.nextLine().trim();
if(line.isEmpty())
continue;
if(line.equalsIgnoreCase("quit"))
break;
check(line);
}
}
}

output

Enter a line to check. Type quit to end the program.
A man, a plan, a canal, Panama!
Input string: A man, a plan, a canal, Panama!
Cleaned string: amanaplanacanalpanama
Stack = a Queue = a
Stack = m Queue = m
Stack = a Queue = a
Stack = n Queue = n
Stack = a Queue = a
Stack = p Queue = p
Stack = l Queue = l
Stack = a Queue = a
Stack = n Queue = n
Stack = a Queue = a
Stack = c Queue = c
Stack = a Queue = a
Stack = n Queue = n
Stack = a Queue = a
Stack = l Queue = l
Stack = p Queue = p
Stack = a Queue = a
Stack = n Queue = n
Stack = a Queue = a
Stack = m Queue = m
Stack = a Queue = a
Yes
Enter a line to check. Type quit to end the program.
Madam
Input string: Madam
Cleaned string: madam
Stack = m Queue = m
Stack = a Queue = a
Stack = d Queue = d
Stack = a Queue = a
Stack = m Queue = m
Yes
Enter a line to check. Type quit to end the program.
good
Input string: good
Cleaned string: good
Stack = d Queue = g
No
Enter a line to check. Type quit to end the program.
racecar
Input string: racecar
Cleaned string: racecar
Stack = r Queue = r
Stack = a Queue = a
Stack = c Queue = c
Stack = e Queue = e
Stack = c Queue = c
Stack = a Queue = a
Stack = r Queue = r
Yes
Enter a line to check. Type quit to end the program.
quit

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.