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)