ISC Practicals and Theory - Palindrome Word/Sentence (OOP)

This version reads a sentence ending in ., ? or !, prints the words that are palindromes with their count, and says whether the whole sentence is a palindrome. The sentence is given to a parameterised constructor; main reads it, creates the object and calls display(). Words are cut out with charAt() and substring(), without split() or StringTokenizer.

Definition

A palindrome reads the same from both ends, ignoring case. A one-letter word is a palindrome.

• Word level: Nitin is a palindrome, ran is not.
• Sentence level: ignoring spaces, the terminator and case, Never odd or even. becomes neveroddoreven, a palindrome, although none of its words is one.

Choices made in this program:

• Spaces at the two ends of the line are ignored: the constructor stores the sentence after trim(). The sentence is valid only if its last character is ., ? or ! and at least one character comes before it; otherwise INVALID INPUT is printed.
• Words are separated by spaces only; other punctuation inside the sentence stays part of the word, and the whole-sentence test ignores only spaces and the terminator.
• Case is ignored by toUpper() (ASCII arithmetic), not equalsIgnoreCase() or toLowerCase(); no library method that reverses a string is used.
• Single-letter words count as palindromes.
• A sentence of only the terminator (.) has no words, so it is INVALID INPUT.

Algorithm

1. main reads the line into s and creates ob with new PalindromeCheck(s). The constructor stores s.trim() in str and sets result to "" and count to 0.
2. display() calls isValid(). If the trimmed line has fewer than 2 characters or does not end in ., ? or !, it prints INVALID INPUT and stops.
3. findWords() sets n = str.length() - 1 (the terminator's position) and i = 0, then repeats while i < n:
   • If str.charAt(i) is a space, i increases.
   • Otherwise j moves on from i until a space or n; the word is str.substring(i, j).
   • isPalin(w) compares characters from both ends inwards using toUpper(); one mismatch gives false.
   • A palindrome word is added to result and count increases. Then i = j.
4. display() prints the words (or none) and Number of palindrome words = count.
5. isSentencePalin() moves i from the left and j from the position before the terminator, skipping spaces, comparing with toUpper(), and returns false on a mismatch or true when i >= j.
6. display() prints The sentence is a palindrome or The sentence is not a palindrome.

Program

The class PalindromeCheck holds the sentence, the palindrome words found and their count. Each method does one job and main supplies the sentence to the constructor.

import java.util.Scanner;

/* Class PalindromeCheck analyses a sentence given to the constructor: it finds
   the words that are palindromes and checks whether the whole sentence is one. */
public class PalindromeCheck
{
    String str;       // the sentence to be analysed (ends in '.', '?' or '!')
    String result;    // the palindrome words found, each followed by a space
    int count;        // number of palindrome words found

    /* Parameterised constructor. Parameter s: the sentence.
       Stores it without the spaces at its two ends and clears result and count. */
    PalindromeCheck(String s)
    {
        str = s.trim();                  // trim() removes the spaces at the two ends
        result = "";
        count = 0;
    }

    /* Returns true if the sentence has at least one character before its last
       character and that last character is '.', '?' or '!', otherwise false. */
    boolean isValid()
    {
        int n = str.length();
        if (n < 2)                       // empty, or only a terminator
            return false;
        char last = str.charAt(n - 1);
        return last == '.' || last == '?' || last == '!';
    }

    /* Parameter c: a character. Returns c as a capital letter if it is a
       small letter (ASCII value reduced by 32), otherwise c unchanged.
       Used to compare characters without regard to case. */
    char toUpper(char c)
    {
        if (c >= 'a' && c <= 'z')
            return (char)(c - 32);
        return c;
    }

    /* Parameter w: a word. Returns true if w reads the same from both ends,
       ignoring case. A one-letter word is a palindrome. */
    boolean isPalin(String w)
    {
        int i = 0;                       // moves from the left end
        int j = w.length() - 1;          // moves from the right end
        while (i < j)
        {
            if (toUpper(w.charAt(i)) != toUpper(w.charAt(j)))
                return false;            // a mismatch: not a palindrome
            i++;
            j--;
        }
        return true;
    }

    /* Extracts the words of the sentence one by one (a word is a run of
       characters between spaces; the last character is the terminator and
       is left out). Each palindrome word is added to result and counted. */
    void findWords()
    {
        int n = str.length() - 1;        // position of the terminator
        int i = 0;
        while (i < n)
        {
            if (str.charAt(i) == ' ')    // skip spaces between words
                i++;
            else
            {
                int j = i;               // j will stop just after the word
                while (j < n && str.charAt(j) != ' ')
                    j++;
                String w = str.substring(i, j);   // the word
                if (isPalin(w))
                {
                    result = result + w + " ";
                    count++;
                }
                i = j;                   // continue after this word
            }
        }
    }

    /* Returns true if the whole sentence, ignoring spaces, the terminator
       and case, reads the same from both ends. */
    boolean isSentencePalin()
    {
        int i = 0;                       // moves from the left end
        int j = str.length() - 2;        // moves from the right, before the terminator
        while (i < j)
        {
            if (str.charAt(i) == ' ')
                i++;                     // skip a space on the left
            else if (str.charAt(j) == ' ')
                j--;                     // skip a space on the right
            else
            {
                if (toUpper(str.charAt(i)) != toUpper(str.charAt(j)))
                    return false;
                i++;
                j--;
            }
        }
        return true;
    }

    /* Prints the palindrome words, their count and the verdict on the
       whole sentence; prints INVALID INPUT if the sentence is not valid */
    void display()
    {
        if (!isValid())
        {
            System.out.println("INVALID INPUT");
            return;
        }
        findWords();
        if (count == 0)
            System.out.println("Palindrome words: none");
        else
            System.out.println("Palindrome words: " + result);
        System.out.println("Number of palindrome words = " + count);
        if (isSentencePalin())
            System.out.println("The sentence is a palindrome");
        else
            System.out.println("The sentence is not a palindrome");
    }

    /* main reads the sentence, creates the object and calls the method */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String s = sc.nextLine();
        PalindromeCheck ob = new PalindromeCheck(s);   // object of this class
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a sentence: Nitin ran.
Palindrome words: Nitin 
Number of palindrome words = 1
The sentence is not a palindrome

Enter a sentence: Never odd or even.
Palindrome words: none
Number of palindrome words = 0
The sentence is a palindrome

Enter a sentence:   I   am   not  a  Bob?
Palindrome words: I a Bob 
Number of palindrome words = 3
The sentence is not a palindrome

Enter a sentence: Madam
INVALID INPUT

Enter a sentence: .
INVALID INPUT

Enter a sentence:  Nitin ran.   
Palindrome words: Nitin 
Number of palindrome words = 1
The sentence is not a palindrome

Dry run

Input Nitin ran. (10 characters, terminator at position 9, so n = 9). The constructor sets result to empty and count to 0.

The output is Palindrome words: Nitin and Number of palindrome words = 1.

For the whole sentence i = 0 and j = 8: N and n match, so i = 1 and j = 7. Then i and a differ, isSentencePalin() returns false and the program prints The sentence is not a palindrome, the same as the real run above.

Variations

1. Reverse the words "Write a program to accept a sentence and print its words in reverse order."
2. Palindrome word "Write a program to accept a word and check whether it is a palindrome."
3. Longest palindrome word "Write a program to accept a sentence and print the longest palindrome word in it."
4. Recursive palindrome "Write a program to check whether a string is a palindrome using recursive technique." See Palindrome String; this note uses a loop, not recursion.