Reverse words in a sentence : Coding in C / C++ – 5

Question. We are given a sentence (stored as a string of characters). We want to reverse the words in that string, i.e. if the sentence is, “This is the input”, the desired output is “input the is This”.

Solution.

One method could be to scan through the input starting from the end. So we will be reading the words in reverse order. Copy each word in that order into a newly created temporary buffer. Once all words are thus copied, copy this buffer into the original string, and free the memory allocated to the buffer.

Another solution, which does not require any temporary buffer, could proceed as follows:

We will reverse the string in-place, and once we have done that, we will reverse each of its words in-place, thus precluding the need to use a buffer.

We note that to reverse each of the words within the string (once we have reversed the string itself), we would need to have a function that takes the start index and the end index of substring which it intends to reverse.

That function could be written as follows :

—–

// this function takes as input a string s, and reverses in-place the substring from index = start to index = //end.

void reverse ( char *s, int start, int end)

{

assert ( start > 0);

assert (end < strlen (s) );

for ( int i = start, j = end; i < j; i++, j – – )

{

//swap the characters s[i] and s[j]

char temp = *(s+i);

*(s+i) = *(s+j);

*(s+j) = temp;

}

}

—–

Now that we have the above reverse function, we can use it to first reverse the entire input sentence, and then reverse each word in that reversed sentence.

For this, we would need to know how to identify that a word has started/ ended. We will assume that there is one blank space between adjacent words.

—–

void sentence_rev ( char *s)

{

if ( ! s )

return;

else

{

reverse ( s, 0, strlen (s) – 1);

// now reverse each word.

int index = 0;

// start_index and end_index represent the indexes for each word which we reverse

int start_index, end_index;

while ( * (s + index) ! = ” )

{

start_index = index;

while ( * (s + index) != ”    &&   *(s+index) ! = ‘ ‘)

//ie. while end-of-word or end-of-string is not reached

index + + ;

end_index = index – 1;

reverse (s, start_index, end_index);

}

}

}

——


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: