Reverse word order in a string in place

Question

I am trying to change the word order in a sentence in place, for example:

These sentence words are reversed.

becomes

vice versa. these are sentence words

This is what I still have that almost works: I use the strrev function to change the string, and then the inprev function to send each word to the strrev function individually, to return them back to their original orientation, but in the reverse order. Sending a pointer to the beginning and end of the strrev function may seem a little silly, but it allows you to use the same function in inprev () by sending a pointer to the beginning 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 result:

Foobar my friends, foobar

raboof, sdneirf ym rabooF

foobarfriends, my foobarfriend

The problem is that the absence of a finite space at the end of the last word means that there is no space between this word and the previous one in the last line and instead rushes to the end of the last word, which was the first word in the original line. Sending space on the other side of the word only moves the problem elsewhere. Can anyone see a solution?

Answer 1

You just need to move the start pointer to the inprev function to skip the space between words. Since this seems like homework (correct me if I am wrong), I will just say that all you have to do is move the location of one operator.

But this creates a problem, namely: inprev performs a buffer overflow because the search does not end properly. The best way to do this is:

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

and it will also take care of several places. In addition, U + 0020 (ASCII 32, space) is not the only space character. There are standard library functions that validate characters. They are located in <ctype.h> and start with is... for example. isspace .

Answer 2

Sometimes things get easier if you don't use pointers, but offsets. The strspn () and strcspn () libraries work more or less to use offsets, and do a great job of ending the line.

 #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 3

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

 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 optional, as you can just pass str-1 to strrev, but it’s a little more clear what happens.

Answer 4

The following algorithm runs in place and runs in 2 steps. First, it changes the whole line. Then he changes every 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 5

 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 } }