Reversing words in a sentence

Question

I'm currently going through K.N. King's C Programming: A Modern Approach. I've made it past the text for the 8th chapter (Arrays), and I'm eager to move on to chapter 9, but I've yet to solve the so-called "programming projects" at the end of each chapter. Unfortunately, the 14th... bugs me.

Write a program that reverses the words in a sentence.

Enter a sentence: you can cage a swallow can't you?
Reversal of sentence: you can't swallow a cage can you?

Hint: Use a loop to read the characters one by one and store them in a one-dimensional char array. Have the loop stop at a period, question mark, or exclamation point (the "terminating character "), which is saved in a separate char variable. Then use a second loop to search backward through the array for the beginning of the last word. Print the last word, then search backward for the next-to-last word. Repeat until the beginning of the array is reached. Finally, print the terminating character.

I've been thinking of defining a word as a sequence of characters between blank spaces. So when a space is reached, go backward, printing each character, until another space is found. My first version of the program only printed the first word. The current version of it only prints the other words. I've been stuck on this for two days, so any help is truly appreciated. Here is my code, as well as an output sample. Hopefully I've properly documented my code. Thanks in advance!

Code

/* Include the standard I/O library */
#include<stdio.h>

/* Define main */
int main(void) {

    /**
     * Declare an array of characters storing the sentence, as well as
     * a character representing the current character under cursor and
     * the terminating character
     */
    char sentence[100] = { ' ' }, c, tc;

    /**
     * Declare a loop counter already initialized at 0, an incremental
     * variable, as well as the size of the read sentence
     */
    int i = 0, j = 1, size = 0;

    /* Get the sentence */
    printf("Enter a sentence: \n");
    for(c = getchar(); (c != '.') && (c != '!') && 
        (c != '?') && (c != '\n'); c = getchar(), i++) {

        sentence[i] = c; /* Store the current character in the array */
        size++; /* Increase the sentence's size */
    }

    tc = c; /* Get the terminating character */

    /**
     * Go backward through the array, printing each sequence of characters
     * between spaces
     */
    for(i = 99; i >= 0; i--) {

        if(sentence[i] == ' ') {

            while(sentence[i + j] != ' ') {

                printf("%c", sentence[i + j]);
                j++;
            }

            j = 1; /* Reset the incremental variable */
            printf(" "); /* Print a tailing space */
        }
    }

    /**
     * Delete the tailing blank space and print the terminating character,
     * as well as a new line 
     */
    printf("\b%c\n", tc);

    return 0; /* Return 0 upon successful program execution */
}

Output:

http://drp.ly/1nYt5J

Answer 1

push each word on a stack and read the stack from index 0 to N-1

Answer 2

Another methodology to think about:

you can cage a swallow can't you?
uoy t'nac wollaws a egac nac uoy?
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
you t'nac wollaws a egac nac uoy?
^^^
you can't wollaws a egac nac uoy?
    ^^^^^
you can't swallow a egac nac uoy?
          ^^^^^^^
you can't swallow a egac nac uoy?
                  ^
you can't swallow a cage nac uoy?
                    ^^^^
you can't swallow a cage can uoy?
                         ^^^
you can't swallow a cage can you?
                             ^^^

For each thing you want to reverse (be it a whole sentence or a word):

1. Find the beginning and end
2. Swap the beginning and end characters
3. Move "inwards" once
4. keep going until you reach "the middle"

Since reversing a chunk of a string is a common operation, it makes sense to make it its own function. And since the only information the function need to do its job is:

1. the string
2. the beginning index
3. the ending index

What do you think the parameters for the function would be?

The other common thing that needs to be done over and over is "finding" something, be it a space or a punctuation mark. You may need to write this yourself, or if you can use library functions, or want a hint, look up:

man strcspn

Answer 3

Here's an example that does what I mentioned. First, reverse each word in place, then reverse the entire string. Here is a reverse() function that reverses a string in place with a given delimiting character. You could extend to use multiple delimiters if you like.

char *reverse(char *str, char delim)
{
  char *end = strchr(str, delim);
  char *ret;
  char tmp;

  if (end == NULL)
    end = strchr(str, '\0');

  ret = end + 1;
  end--;

  while (end > str)
  {
    tmp = *str;
    *str = *end;
    *end = tmp;

    end--;
    str++;
  }

  return ret;
}

Here is a use case with a little example program:

int main(int argc, char **argv)
{
  char *end = strchr(argv[1], '\0');
  char *str = argv[1];

  while (str < end)
    str = reverse(str, ' ');

  reverse(argv[1], '\0');
  printf("%s\n", argv[1]);

  return 0;
}

Usage example:

$ ./example "the quick red fox jumps over the lazy brown dog"
dog brown lazy the over jumps fox red quick the

Answer 4

int main()
{

    char sent[50],last,s;
    int i,j,length,k,temp,b;
    clrscr();
    i=0;
    printf("Enter a sentence: ");
    sent[i]=getchar();
    while(sent[i]!='\n'&&sent[i]!='.'&&sent[i]!='?'&&sent[i]!='!')
    {
        sent[++i]=getchar();
    }
    last=sent[i];//storing last char
    b=i; //length of string
    printf("Reverse of sentence: ");
    for(;;)
    {
        k=b-1;// begin from last position
        temp=k;
        while(sent[k]!=' ' && k!=-1)
        k--;
        s=k;//storing space here
        b=s;
        for(j=b+1;j<=temp;j++)
        putchar(sent[j]);
        if(s!=-1)
        putchar(sent[s]);
        if(b==-1)
        break;
    }
    putchar(last);
    getch();
    return 0;
}

Answer 5

By taking the input as character array and then reversing the whole array. Following this, reverse word by word where splitting of the sentence into words occur at " ","?","\0" etc. Hope this helps.

 void reverse(char s[],int start,int stop){
 char t;
 while(start<stop){
    t = s[start];
    s[start]=s[stop];
    s[stop]=t;
    start++;
    stop--;
}
}

int main() {

char str[100];
gets(str);

int pos=0,begin=0,end;
reverse(str,begin,strlen(str)-1); //since the last character is null

while(pos<=strlen(str)){
    if((str[pos]==' ')||(str[pos]=='\0')||(str[pos]=='?')||(str[pos]=='!')){
        end = pos - 1; 
       reverse(str,begin,end);  
        begin = pos+1; //for the next word
    }

    pos++;

}   

cout<<str;
return 0;
}

Answer 6

Here is my answer

/* write a program that reverses the words in a sentence:

Enter a sentence: you can cage a swallow can't you?

Reversal of sentence: you can't swallow a cage can you?

Hint: Use a loop to read the characters one by one and store them in a one-dimensional char array.

Have the loop stop at a period, question mark, or exclamation point -- (the "terminating character"), which is saved as a separate char variable.

Then use a second loop to search backward through the array for the beginning of the last word.

Print the last word, then search backward for the next to last word. Repeat until the beginning of the array is finally reached.

Finally print the terminating character.

*/
#include<stdio.h>

int main()
{
int ch;
char sentence[200]; //hard set a limit of 200 character sentence
char word[10] = {'\0','\0','\0','\0','\0','\0','\0','\0','\0'}; //hard set limit of 10 character words
int i = 0; //character position in input
int w = 9; //character position in word
char terminator = '\0';
printf("Enter a sentence:");
   while  ( (ch=getchar()) != '\n' )
       {
       if ( ch == '.' || ch == '?' || ch == '!')
          terminator = ch;
       else
         {
         sentence[i] = ch;
         i++;
         }
//       printf("%d",i);
       }
       sentence[i] = '\0';//set last character to null


    int x;
    for ( x=i ; x >= 0 ; x-- )
        {
           if ( sentence[x] == ' ' )
           {
            printf(" ");//print the space followed by what is in the word buffer/array
//          printf("word length %d ",w);
            printf("%c",word[0]); //probably should have a for loop here
            printf("%c",word[1]);
            printf("%c",word[2]);
            printf("%c",word[3]);
            printf("%c",word[4]);
            printf("%c",word[5]);
            printf("%c",word[6]);
            printf("%c",word[7]);
            printf("%c",word[8]);
            printf("%c",word[9]);
            w = 9 ;
            word[0] = '\0'; //fill the word buffer/array with null
            word[1] = '\0';
            word[2] = '\0';
            word[3] = '\0';
            word[4] = '\0';
            word[5] = '\0';
            word[6] = '\0';
            word[7] = '\0';
            word[8] = '\0';
            word[9] = '\0';
//          printf("\n");
//          printf("sentence position %d ",x);
           }
           else //assign the letters from sentence[] to letters in word[]
           {
            word[w] = sentence[x];
            w--;
//          printf("word length %d ",w);
//          printf("%c",sentence[x]);
           }
         }
//print the first word because im using space to delimit the words unless i have a space at the
//beginning of the sentence the code above will skip the first word inputed
    printf(" ");//print the space followed by what is in the word buffer/array
    printf("%c",word[0]);
    printf("%c",word[1]);
    printf("%c",word[2]);
    printf("%c",word[3]);
    printf("%c",word[4]);
    printf("%c",word[5]);
    printf("%c",word[6]);
    printf("%c",word[7]);
    printf("%c",word[8]);
    printf("%c",word[9]);



if ( terminator != '\0' ) //prints a . ? or ! if it is including in the inputed sentence
    printf("%c",terminator);

    printf("\n");
    printf("\n");
return 0;

Answer 7

Reverse words in a string (words are separated by one or more spaces) - this problem can be handled various ways, few of the solutions i have seen so far use extra memory. The idea is to get the optimum solution, like without using extra memory (in place) solution with time complexity O(N).

So Let's take the example, lets say string is "Hello World" - and expected O/P "World Hello"

• First we will just reverse the entire sentence IN PLACE, like "dlroW olleH" (We have used XOR operation for swapping. please have a look at Swap() method)
• Now we increase the index and stop when we come across ' '(space).
• Once we encounter any space, we know that we got a word. Let's invoke the reverse function on that word and Reverse that word. So in that case it will be like, "World olleH"
• Now we go further and stop when our index reach till the length of the sentence.
• Once we reach at end, grab the last index -1 and reverse the last word, so it will be like "World Hello"

One important point to note here, when we invoke the Reverse Function to reverse the word, we will be required to provide the starting index and the ending index of that particular word in respective sentence.

The sample code would look like as mentioned below. I haven't tested with edge cases - but it will provide basic idea of approach.

  using System;

  namespace SampleString
  {
    class ReverseWordsInSetence
    {
        // Reverse words in a string (words are separated by one or more spaces).
        private static String GetReverseWordsInSetence(string sentence)
        {
            char[] stringArray = sentence.ToCharArray();
            int len = sentence.Length;
            int startIndex = 0;

            Swap(ref stringArray, ref startIndex , len-1);
            startIndex = 0;

            for (int currentIndex = 0; currentIndex < len; currentIndex++)
            { 
                if (stringArray[currentIndex].Equals(' '))
                {
                    Swap(ref stringArray, ref startIndex, currentIndex-1);
                }
                else if (currentIndex == len - 1)
                {
                    Swap(ref stringArray, ref startIndex, currentIndex);
                }

            }

            return new string(stringArray);
        }


        private static void Swap(ref char[] a, ref int i, int j)
        {
            int tempIndex = j;

            while (i < j)
            {
                if (a[j].Equals('.'))
                {
                    j--;
                }
                else
                {
                    a[i] ^= a[j];
                    a[j] ^= a[i];
                    a[i++] ^= a[j--];
                }
            }

            i = tempIndex + 2;
        }

        static void Main(string[] args)
        {        
           Console.WriteLine(GetReverseWordsInSetence("Hello World."));
           Console.ReadLine();
        }
    }
}

Answer 8

I havent tried it. hope would be helpful to u.

char temp[100];
int j=0, k=100, l=0;
for(i=size-1; i>=0; i--){
  if(sentence[i] == ' ' || i == 0){
    if(k-i >= 2){// at least one character

      if(i==0) j = 0;
      else j = i+1;

      for( l=0; j < k; j++, l++){
         temp[l] = sentence[j];
      }
      temp[l] = '\0';
      printf("%s ",temp);
    }
    k = i;
  }
}
printf("\b%c",tc);

Answer 9

The following code pushes the words on a stack and then reads out the stack backwards, as Quonux hinted at.

#include <stdlib.h>

int main()
{
char s[20][20];
int i=0,length=-1;
for(i=0;;i++)
{
    scanf("%s",s[i]);
    length++;
    if(getchar()=='\n')
        break;
}
for(i=length;i>=0;i--)
    printf("%s ",s[i]);
return 0;
}

Answer 10

The answers so far have contributed alternative algorithms, which can be sorted into two classes:

1. Reverse the entire sentence and reverse all the words in it. Some versions first reverse the words while others first reverse the sentence; the order in which these reversals are applied does not matter. The net effect is that the words appear in reverse order but the characters within each word are in their normal order.
2. Put the words on a stack, then take them from the stack again so that the last word becomes the first.

Rather than suggesting yet another alternative algorithm (which would probably fall in one of the above two categories), I will explain why the code in the original question does not work as intended.

First, observe that the code in the question is actually a variant of class 1. It first reverses the entire sentence and then reverses each word:

/* Outer loop goes backwards through the array, effectively reversing the sentence */
for(i = 99; i >= 0; i--) {

    if(sentence[i] == ' ') {

        /* Inner loop goes forward, reversing the word again */
        while(sentence[i + j] != ' ') {

            printf("%c", sentence[i + j]);
            j++;
        }

        j = 1;
        printf(" ");
    }
}

Apart from some beginner mistakes, this is actually an optimal way to reverse the words of a sentence. It uses no additional memory and it does not waste time.

The asker noted that the algorithm works as intended, except that it does not print the first word of the original sentence (which should become the last word). The reason for this is that the array traversals stop on ' ' in both directions. When the outer loop reaches the start of the sentence, it finds no space, because the first character of the user input overwrites the space in sentence[0]:

/* ... */
char sentence[100] = { ' ' }, c, tc;

/* ... */
int i = 0, j = 1, size = 0;

/* Get the sentence */
printf("Enter a sentence: \n");
for(c = getchar(); (c != '.') && (c != '!') && 
    (c != '?') && (c != '\n'); c = getchar(), i++) {

    sentence[i] = c; /* Store the current character in the array */
    size++; /* Increase the sentence's size */
}

Hence, when i becomes 0 in the outer loop, there is no space, and the inner loop which should print the word starting at sentence[0] is never entered. i then decrements to -1 and the outer loop terminates.

You can test this without changing the code by simply running the program as a user. If you enter a space as the first character, the response of the program will be correct:

Enter a sentence:
 you can cage a swallow can't you?
you can't swallow a cage can you?

There are two ways in which you can enforce the inclusion of the first word in your code. The first is to simply always put a space at the beginning of your sentence array. You can do that by starting to copy the user input at i = 1 instead of i = 0:

/**
 * Declare a loop counter already initialized at 1, an incremental
 * variable, as well as the size of the read sentence
 */
int i = 1, j = 1, size = 0;

Another, slightly less elegant way would be to simply repeat the inner loop after the outer loop terminates:

/**
 * Go backward through the array, printing each sequence of characters
 * between spaces
 */
for(i = 99; i >= 0; i--) {

    if(sentence[i] == ' ') {

        while(sentence[i + j] != ' ') {

            printf("%c", sentence[i + j]);
            j++;
        }

        j = 1; /* Reset the incremental variable */
        printf(" "); /* Print a tailing space */
    }
}

/* print the last word */
while(sentence[i + j] != ' ') {

    printf("%c", sentence[i + j]);
    j++;
}

You can make that less repetitive by factoring out the inner loop to a new function. Here's the entire algorithm with inner loop factored out to the print_word function, skipping the comments and blank lines:

#include<stdio.h>

void print_word(char[] sentence, int i) {
    int j = 1;
    while(sentence[i + j] != ' ') {
        printf("%c", sentence[i + j]);
        j++;
    }
}

int main(void) {
    char sentence[100] = { ' ' }, c, tc;
    int i = 0, j = 1, size = 0;
    printf("Enter a sentence: \n");
    for(c = getchar(); (c != '.') && (c != '!') && 
        (c != '?') && (c != '\n'); c = getchar(), i++) {
        sentence[i] = c; /* Store the current character in the array */
        size++; /* Increase the sentence's size */
    }
    tc = c; /* Get the terminating character */
    for(i = 99; i >= 0; i--) {
        if(sentence[i] == ' ') {
            print_word(sentence, i);
            printf(" "); /* Print a tailing space */
        }
    }
    print_word(sentence, i);
    printf("\b%c\n", tc);
    return 0; /* Return 0 upon successful program execution */
}

As a final remark, there's one more thing that you could do better. Right now, the outer loop starts at i = 99, the last possible character in the sentence array. However, while reading the user input you updated i to point to the next input position, so just before the start of the outer loop, i is already pointing to the first character after the sentence. Why not use that and simply start at i - 1?