Reversing the word order in a string in place

Question

I'm trying to reverse the order of words in a sentence in place, eg:

This sentences words are reversed.

becomes

reversed. are words sentences This

This is what I have so far, which almost works: I use the strrev function to reverse the string, and then the inprev function to send each word to the strrev function individually, to reverse them back to the original orientation, but in reversed order. Sending a pointer for the start and end of the strrev function might seem a bit silly, but it allows the same function to be used in inprev(), sending off a pointer to the start and end of individual words.

#include <stdio.h>
#include <string.h>

void strrev(char * start, char * end);
void inprev(char * start);

int main(void)
{
   char str[] = "Foobar my friends, foobar";
   char * end = (str + strlen(str) -1);
   puts(str);
   strrev(str, end);
   puts(str);
   inprev(str);

   puts(str);

   return 0;
}

void strrev(char * start, char * end)
{
   char temp;

while (end > start)
   {
     temp = *start;
     *start = *end;
     *end = temp;
      start++;
      end--;
   }
}

void inprev(char * start)
{
     char * first = start;
     char * spcpnt = start;
     while (*spcpnt)
     {
        while (*spcpnt != ' ' && *spcpnt)
           spcpnt++;
        strrev(start, spcpnt-1);         // removing the -1 sends the space on the 
        start = spcpnt++;                // other side to be reversed, doesn't stop 
                                         // the problem.  

     }

}

Here is the output:

Foobar my friends, foobar

raboof ,sdneirf ym rabooF

foobarfriends, my Foobar

The problem is that the lack of a final space at the end of the final word means that a space is missing between that word and the preceeding one in the final string, and instead gets thrown onto the end of the last word, which was the first word in the original string. Sending off the space on the other side of the word only moves the problem elsewhere. Can anyone see a solution?

Answer 1

The code is almost correct except for the line start = spcpnt++; Change this to start = ++spcpnt; and it works. the original assignment was copying the character and then incrementing the pointer. So, start was pointing to space instead of the first character of the next string. Note that there is a difference between increment operation with no assignment to assignment to another variable with increment operation!

Here is the full code:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

void strrev(char * start, char * end);
void inprev(char * start);

void strrev(char * start, char * end)
{
    char temp;
    
    while (end > start)
    {
        temp = *start;
        *start = *end;
        *end = temp;
        start++;
        end--;
    }
}

void inprev(char * start)
{
    char * spcpnt = start;
    while (*spcpnt)
    {
        while (!isspace(*spcpnt) && *spcpnt)
        {
            spcpnt++;
        }
        
        strrev(start, spcpnt-1);
        
        start = ++spcpnt;
    }

}

int main(void)
{
   char str[] = "Foobar my friends, foobar";
   
   char * end = (str + strlen(str) -1);
   puts(str);
   
   strrev(str, end);
   puts(str);
   
   inprev(str);
   puts(str);

   return 0;
}

The output for this program is:

Foobar my friends, foobar
raboof ,sdneirf ym rabooF
foobar friends, my Foobar

Answer 2

void reverse_str(char* const p, int i, int j) // helper to reverse string p from index i to j
{
    char t;
    for(; i < j ; i++, j--)
        t=p[i], p[i]=p[j], p[j]=t;
}

void reverse_word_order(char* const p) // reverse order of words in string p
{
    int i, j, len = strlen(p);  // use i, j for start, end indices of each word

    reverse_str(p, 0, len-1);      // first reverse the whole string p
    for(i = j = 0; i < len; i = j) // now reverse chars in each word of string p
    {
        for(; p[i] && isspace(p[i]);) // advance i to word begin
            i++;
        for(j = i; p[j] && !isspace(p[j]);) // advance j to past word end
            j++;
        reverse_str(p, i, j-1);  // reverse chars in word between i, j-1
    }
}

Answer 3

The following algorithm is in-place and runs in 2 steps. First it reverses the entire string. Then it reverses each word.

#include <stdio.h>

void reverse(char *str, int len)
{
    char *p = str;
    char *e = str + len - 1;

    while (p != e) {
        *p ^= *e ^= *p ^= *e;
        p++;
        e--;
    }
}

void reverse_words(char *str)
{
    char *p;

    // First, reverse the entire string
    reverse(str, strlen(str));

    // Then, reverse each word
    p = str;
    while (*p) {
        char *e = p;
        while (*e != ' ' && *e != '\0') {
            e++;
        }

        reverse(p, e - p);
        printf("%.*s%c", e - p, p, *e);

        if (*e == '\0')
            break;
        else
            p = e + 1;
    }
}

int main(void) {
    char buf[] = "Bob likes Alice";
    reverse_words(buf);
    return 0;
}

Answer 4

Sometimes things get easier if you don't use pointers but offsets. The strspn() and strcspn() library functions more or less force you to use offsets, and deal with the end-of-string condition quite nicely.

#include <stdio.h>
#include <string.h>

size_t revword(char *str);
void revmem(void *ptr, size_t len);

size_t revword(char *str) {
size_t pos,len;

for (pos=len=0; str[pos]; pos += len) {
        len = strspn( str+pos, " \t\n\r");
        if (len) continue;
        len = strcspn( str+pos, " \t\n\r");
        if (!len) continue;
        revmem( str+pos, len );
        }
revmem( str, pos );
return len;
}

void revmem(void *ptr, size_t len)
{
size_t idx;
char *str = (char*) ptr;

if (len-- < 2) return;

for (idx = 0; idx < len; idx++,len--) {
        char tmp = str[idx];
        str[idx] = str[len];
        str[len] = tmp;
        }
}

int main (int argc, char **argv)
{

if (!argv[1]) return 0;
revword(argv[1] );
printf("'%s'\n", argv[1] );

return 0;
}                                                                                           

Answer 5

Figured out a solution; here is my revised function that works properly.

void inprev(char * str)
{
    _Bool inword = 0;
    char * wordend;
    char * wordstart;

     while(*str)
     {
         if(!isspace(*str) && (inword == 0))
         {
             wordstart = str;
             inword = 1;
         }
         else if (isspace(*str) && (inword == 1))
         {
             wordend = str-1;
             inword = 0;
             strrev(wordstart, wordend);
         }

         str++;
     }

     if (*str == '\0')
        strrev(wordstart, str-1);

}

char * wordend is uneccessary as you can just pass str-1 to the strrev function, but it makes it a bit more clear what's happening.

Answer 6

You just need to move the start pointer in the inprev function to skip the space between words. As this appears to be homework (correct me if I'm wrong) I'll just say that all you need to do is move the location of one operator.

But, this produces a problem, namely, the inprev performs a buffer overrun because the search isn't terminated properly. A better way to do it is:

while not end of string
  search for start of word
  start = start of word
  search for end of word
  strrev (start, end)

and that will take care of multiple spaces too. Also, U+0020 (ASCII 32, a space) is not the only white space character. There are standard library functions that test characters. They are in <ctype.h> and start with is..., e.g. isspace.