PART 3-Stacks and Stack Implementations, 10 points A palindrome is a string of characters (a word, phrase, or sentence) that is the same regardless of whether you read it forward or backward-assuming that you ignore spaces, punctuation (https://simple.wikipedia.org/wiki/Punctuation. Do not worry about ellipsis, n-dash, and m-dash.), and case. For example, Race car is a palindrome. So is A man, a plan, a canal Panama. (More palindromes, http://www.palindromelist.net/ Write a Java program that uses a stack to test whether an input string is a palindrome. Sample output Enter a string that you want to check (or enter ! to exit): Ah, Satan sees Natasha! Ah, Satan sees Natasha! IS a palindrome! Enter a string that you want to check (or enter to exit): Amy, must I jujitsu my ma? Amy, must I jujitsu my ma? IS a palindrome! Enter a string that you want to check (or enter! to exit): A man, a plan, a canal: Panama A man, a plan, a canal: Panama. IS a palindrome! Enter a string that you want to check (or enter to exit): Are Mac 'n' Oliver evil on camera? Are Mac 'n' oliver evil on camera? IS a palindrome! Enter a string that you want to check (or enter to exit): CSC220 Data Sructures CSC220 Data Sructures is NOT a palindrome! Enter a string that you want to check (or enter to exit):! Done