import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        System.out.print("Enter a string: ");
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        String input = scanner.nextLine();

        Boolean isPalindrome = palindrome(input);

        String not = "";

        if (!isPalindrome) {
            not = "not ";
        }

        System.out.println(input + " is " + not + "a palindrome");

        scanner.close();
    }

    // Returns true if the given string is a palindrome.
    // Method ignores spaces and capitalization.
    public static boolean palindrome(String s) {
        s = s.toLowerCase().replaceAll(" ", "");

        Stack<Character> stack = new Stack<>();

        char[] letters = s.toCharArray();

        for (int i = 0; i < s.length() / 2; i++) {
            stack.push(letters[i]);
        }

        int plus = 0;

        if (s.length() % 2 != 0) {
            plus = 1;
        }

        for (int i = (s.length() / 2) + plus; i < s.length(); i++) {
            if (stack.empty()) {
                return true;
            }

            if (letters[i] == stack.peek()) {
                stack.pop();
            } else {
                return false;
            }
        }

        return true;
    }
}