Reversing every word in a string

Question

Examples:

char test1[] = " ";
char test2[] = " hello z";
char test3[] = "hello world ";
char test4[] = "x y z ";

Results:

" "
" olleh z"
"olleh dlrow "
"x y z "

The problem:

Reverse every world in a string, ignore the spaces.

The following is my code. The basic idea is to scan the string, when finding a word, then reverse it. The complexity of the algorithm is O(n), where n is the length of the string.

Could anyone help me verify it? Is there any better solution?

void reverse_word(char* s, char* e)
{
 while(s < e)
 {
 char tmp = *s;
 *s = *e;
 *e = tmp;
 ++s;
 --e;
 }
}
char* word_start_index(char* p)
{
 while((*p != '0円') && (*p == ' '))
 {
 ++p; 
 }
 if(*p == '0円')
 return NULL;
 else
 return p;
}
char* word_end_index(char* p)
{
 while((*p != '0円') && (*p != ' '))
 {
 ++p;
 }
 return p-1;
} 
void reverse_string(char* s)
{
 char* s_w = NULL;
 char* e_w = NULL;
 char* runner = s;
 while(*runner != '0円')
 {
 char* cur_word_s = word_start_index(runner);
 if(cur_word_s == NULL)
 break;
 char* cur_word_e = word_end_index(cur_word_s);
 reverse_word(cur_word_s, cur_word_e);
 runner = cur_word_e+1; 
 }
}

• Ron Klein: I'd skip the spaces in the main loop, instead of having them in the start index calculations.
• William Morris: Your functions word_end_index and word_start_index are effectively rewriting strcspn and strspn. Checkout the standard library!
• psoft: Interview in Boulder much?

Answer 1

If using C++ is an option for you (which your tags suggest), then you might consider using std::swap for swapping the characters. You might also want to use isspace to check for whitespace other than ' '.

You could also write it all in a single function:

void reverse_every_word(char* s)
{
 char* front;
 char* back;
 while(*s != '0円')
 {
 // handle whitespace
 while(*s != '0円' && isspace(*s))
 s++;
 // skip to the end of the current word
 front = s;
 while(*s != '0円' && !isspace(*s))
 s++;
 // reverse
 back = s-1;
 while (front < back)
 std::swap(*front++, *back--);
 }
}

Answer 2

Comments on code

In C++ code you do not want to be messing with C-Strings. All that memory management makes the code hard to maintain and is difficult to get correct. prefer to use std::string which does all the hard work and lets you concentrate on the algorithm.

void reverse_word(char* s, char* e)

There are already algorithms for reversing stuff std::reverse() and swapping the two values std::swap() so there is no need to implement either.

 while(s < e)
 {
 char tmp = *s;
 *s = *e;
 *e = tmp;
 ++s;
 --e;
 }

Space ' ' is not the only white space character. Rather than explicitly testing for a space you should use the standard function for testing if a character is white space std::is_space()

 while((*p != '0円') && (*p == ' '))
 

Comments on Algorithm

There is already a std::reverse() algorithm.
Using this would reduce the complexity of your code to just finding the beginning and end of each word. Since operator>> does this automatically it makes the code very trivial:

void reverse_string(std::string& paragraph)
{
 std::stringstream pStream(paragraph);
 std::string word;
 paragraph.clear();
 while(pStream >> word)
 {
 std::reverse(word.begin(), word.end());
 paragraph.append(word);
 paragraph.append(" ");
 }
}

• Fihop: Thanks very much Loki. For the function reverse_string, does it keep the original white space?
• Loki Astari: No. Space is dropped.

Answer 3

Having C++11, we could do,

template<class InputIterator, class UnaryPredicate>
void reverseSeparate(InputIterator first, InputIterator last, UnaryPredicate pred)
{
 first = std::find_if_not(first,last,pred);
 while(first!=last){
 InputIterator t = std::find_if(first,last,pred);
 std::reverse(first,t);
 first = std::find_if_not(t,last,pred);
 }
}

using this, we can (among other things) reverse every word in a string.

std::string s = "hi hello world ";
reverseSeparate(s.begin(),s.end(), [](char c){return c==' ';});