Note: you must solve this problem

• using the linked implementation of a stack from Chapter 13
• using only ONE stack as described below

Write a Java program that reads in a String (containing the word or phrase to be tested) entered by the user and then determines if the word or phrase is a palindrome (omit any blanks, capitals or punctuation). A palindrome contains the same characters forwards as backwards, for example level is a palindrome.

Your solution that determines if a word or sentence is a palindrome (once all blanks, etc are removed) must use only one stack, you MUST process the string from left to right, and are allowed to go through the string only once. You must use an efficient algorithm.

Test your program on the following palindromes. Also test some strings that are not palindromes.

You are allowed to enter the phrase without blanks, punctuation marks, or capital letters, if you wish, or you can write a method to remove all those first, then test the String for a palindrome.

Think carefully about the difference between phrases with even or odd number of characters.

deed

repaper

Was it a car or a cat I saw?

I did, did I?

Hints: 1. there is a length( ) method, a charAt, and a toLowerCase() method in the String class.

2. the Character.isLetter(char) can be useful here

**THIS IS THE STACK CODE THAT YOU HAVE TO USE

package jsjf;

import jsjf.exceptions.*;

import java.util.Iterator;

/**

* Represents a linked implementation of a stack.

*

*/

public class LinkedStack implements StackADT

{

private int count;

private LinearNode top;

// Creates an empty stack.

public LinkedStack()

{

count = 0;

top = null;

}

/**

* Adds the specified element to the top of this stack.

* @param element element to be pushed on stack

*/

public void push(T element)

{

LinearNode temp = new LinearNode(element);

temp.setNext(top);

top = temp;

count++;

}

/**

* Removes the element at the top of this stack and returns a

* reference to it.

*/

public T pop() throws EmptyCollectionException

{

if (isEmpty())

throw new EmptyCollectionException("stack");

T result = top.getElement();

top = top.getNext();

count--;

return result;

}