ISC Practicals and Theory - Word Potential Sort (OOP)

This program reads a sentence, separates it into words with charAt(), indexOf(), length() and substring() only, finds the potential of each word (the sum of the alphabet positions of its letters) and prints the words in ascending order of potential. This is the object-oriented version: main reads the sentence and passes it to a parameterised constructor, and the methods return their results (true/false, the word count, the potential of a word) instead of printing messages themselves. It sorts with a stable bubble sort.

Definition

The potential of a word is the sum of the positions of its letters in the alphabet: A = 1 ... Z = 26, capital and small letters alike. Ab = 1 + 2 = 3, ba = 2 + 1 = 3 and Zoo = 26 + 15 + 15 = 56.

Characters that are not letters (digits, commas) are ignored: they add 0, so Hi, = 8 + 9 = 17 and 12 = 0.

The sentence must end with ., ? or ! (after the spaces at the two ends of the line have been removed with trim()), which is not part of any word. Words are separated by one or more spaces. Other punctuation inside the sentence stays attached to its word. Words of equal potential keep the order in which they were typed (a stable sort).

Algorithm

1. main reads the sentence into str and creates ob = new WordPotential(str). The constructor stores it in sent after trim() and creates the arrays w and p (50 places each).
2. ob.isValid() returns true if the trimmed line is not empty and ends with ., ? or !. Otherwise main prints INVALID INPUT.
3. ob.extract() stores the words in w and returns their number:
   • s = sent.substring(0, sent.length() - 1) removes the terminator.
   • i moves along s; a space is skipped (so extra spaces do no harm).
   • At a letter or other non-space character a word starts at i. s.indexOf(' ', i) gives the next space e (if -1, the word runs to the end, so e = len). s.substring(i, e) goes into w[n], then n increases and i = e.
   • If a 51st word is found it returns -1, and main prints Too many words. Maximum 50 words allowed.
   • A sentence with no word (for example just .) returns 0, and main prints INVALID INPUT.
4. ob.findPotentials() stores potential(w[i]) in p[i] for every word. potential() adds c - 'A' + 1 for a capital letter and c - 'a' + 1 for a small letter, using comparisons on the char value, with no Character methods.
5. ob.display(...) prints the words with their potentials in typed order.
6. ob.sort() is a bubble sort of w and p together:
   • Pass pass compares neighbours j and j + 1 for j from 0 to n - pass - 1.
   • They are swapped (both arrays) only when p[j] > p[j + 1], strictly greater, so equal potentials never swap and the sort is stable.
7. ob.display(...) prints the sorted list.

Program

The constructor WordPotential(String s) receives the sentence. isValid() and extract() return values for main to act on, potential() returns the score of one word, and sort() and display() work on the data members.

import java.util.Scanner;

/* Class WordPotential finds the potential of each word of a sentence (sum of
   the alphabet positions of its letters) and prints the words in ascending
   order of potential. The sentence is given to the parameterised constructor
   and the methods return their results. No split() or StringTokenizer is used. */
public class WordPotential
{
    String sent;     // the sentence entered by the user, terminator included
    String w[];      // stores the words of the sentence (at most 50)
    int p[];         // p[i] stores the potential of the word w[i]
    int n;           // number of words extracted

    /* Parameterised constructor. Parameter s: the sentence to be processed. */
    WordPotential(String s)
    {
        sent = s.trim();                 // trim() removes the spaces at the two ends
        w = new String[50];
        p = new int[50];
        n = 0;
    }

    /* Returns true if the sentence is not empty and its last character is
       '.', '?' or '!', otherwise false. */
    boolean isValid()
    {
        int len = sent.length();
        if (len == 0)                          // empty line
            return false;
        char last = sent.charAt(len - 1);      // the terminator
        return last == '.' || last == '?' || last == '!';
    }

    /* Extracts the words into w (terminator left out, extra spaces skipped).
       Returns the number of words, or -1 if there are more than 50 words. */
    int extract()
    {
        String s = sent.substring(0, sent.length() - 1);  // sentence without terminator
        int len = s.length();
        int i = 0;                       // index of the character being examined
        n = 0;
        while (i < len)
        {
            if (s.charAt(i) == ' ')      // extra space: skip it
                i++;
            else
            {
                int e = s.indexOf(' ', i);   // the space that ends this word
                if (e == -1)                 // no space left: word ends with the sentence
                    e = len;
                if (n == 50)                 // array is full
                    return -1;
                w[n] = s.substring(i, e);    // the word, from i up to e - 1
                n++;
                i = e;                       // continue after the word
            }
        }
        return n;
    }

    /* Parameter s: a word. Returns its potential: A or a = 1 ... Z or z = 26.
       Characters that are not letters (digits, commas, ...) are ignored. */
    int potential(String s)
    {
        int sum = 0;
        for (int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            if (c >= 'A' && c <= 'Z')
                sum = sum + (c - 'A' + 1);      // capital letter
            else if (c >= 'a' && c <= 'z')
                sum = sum + (c - 'a' + 1);      // small letter
        }
        return sum;
    }

    /* Finds the potential of every word and stores it in p */
    void findPotentials()
    {
        for (int i = 0; i < n; i++)
            p[i] = potential(w[i]);
    }

    /* Bubble sort of w and p (together) in ascending order of potential.
       Neighbours are swapped only when the left one is strictly greater, so
       words of equal potential keep their original order (stable sort). */
    void sort()
    {
        for (int pass = 1; pass < n; pass++)          // n - 1 passes
        {
            for (int j = 0; j < n - pass; j++)        // largest value moves to the end
            {
                if (p[j] > p[j + 1])
                {
                    int tp = p[j];                    // swap the potentials
                    p[j] = p[j + 1];
                    p[j + 1] = tp;
                    String tw = w[j];                 // swap the words with them
                    w[j] = w[j + 1];
                    w[j + 1] = tw;
                }
            }
        }
    }

    /* Parameter heading: the line printed above the list.
       Prints every word with its potential, one per line. */
    void display(String heading)
    {
        System.out.println(heading);
        for (int i = 0; i < n; i++)
            System.out.println(w[i] + " = " + p[i]);
    }

    /* main reads the sentence, creates the object with it and calls the methods */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String str = sc.nextLine();                     // sentence typed by the user
        WordPotential ob = new WordPotential(str);      // object of class WordPotential
        if (!ob.isValid())
            System.out.println("INVALID INPUT");
        else
        {
            int count = ob.extract();                   // number of words, -1 if too many
            if (count == -1)
                System.out.println("Too many words. Maximum 50 words allowed.");
            else if (count == 0)
                System.out.println("INVALID INPUT");
            else
            {
                ob.findPotentials();
                ob.display("Words with their potential:");
                ob.sort();
                ob.display("Words in ascending order of potential:");
            }
        }
    }
}

Variable description table

Sample input and output

Enter a sentence: I love Java programming.
Words with their potential:
I = 9
love = 54
Java = 34
programming = 131
Words in ascending order of potential:
I = 9
Java = 34
love = 54
programming = 131

Enter a sentence:   Ab   ba cd  Dc a  Zoo!
Words with their potential:
Ab = 3
ba = 3
cd = 7
Dc = 7
a = 1
Zoo = 56
Words in ascending order of potential:
a = 1
Ab = 3
ba = 3
cd = 7
Dc = 7
Zoo = 56

Enter a sentence: Go?
Words with their potential:
Go = 22
Words in ascending order of potential:
Go = 22

Enter a sentence: Hello
INVALID INPUT

Enter a sentence: Hi, ok 12.
Words with their potential:
Hi, = 17
ok = 26
12 = 0
Words in ascending order of potential:
12 = 0
Hi, = 17
ok = 26

Enter a sentence: Go?   
Words with their potential:
Go = 22
Words in ascending order of potential:
Go = 22

Dry run

Input: Hi, ok 12. The terminator is removed, leaving Hi, ok 12 (9 characters). extract() finds Hi, (i = 0, e = 3), ok (i = 4, e = 6) and 12 (i = 7, e is -1 so 9). It returns 3.

findPotentials(): Hi, = 8 + 9 = 17 (the comma adds 0), ok = 15 + 11 = 26, 12 = 0. So w = Hi,, ok, 12 and p = 17, 26, 0.

Bubble sort, n = 3:

The sorted order is 12 = 0, Hi, = 17, ok = 26, the same as the real run of the last sample above.

Variations

1. Sort by length "Write a program to read a sentence and print its words in ascending order of length."
2. Alphabetical order "Write a program to arrange the words of a sentence in alphabetical order."
3. Highest potential "Write a program to print the word of a sentence that has the highest potential."
4. Palindrome words "Write a program to count the words of a sentence that are palindromes."