SaltyCrane Blog — Notes on JavaScript and web development

How to reverse words in a sentence using Python and C

Date:  |  Tags: algorithms, c_cplusplus, python  |  8 Comments

This is a technical problem I attempted recently. The problem was to reverse the words in a sentence. For example, The quick brown fox jumped over the lazy dog. becomes dog. lazy the over jumped fox brown quick The. I had to solve the problem first using Python, and then using C. In addition, the C version could only use 1 extra character of memory. I solved the Python version easily, but the C version was too difficult for me. Here are possible solutions.

Python version

sentence = "The quick brown fox jumped over the lazy dog."
words = sentence.split()
sentence_rev = " ".join(reversed(words))
print sentence_rev

C version

Credit for this solution goes to Hai Vu

#include <stdio.h>

/* function declarations */
void reverse_words(char *sentence);
void reverse_chars(char *left, char *right);

/* main program */
int main()
{
   char mysentence[] = "The quick brown fox jumped over the lazy dog.";

   reverse_words(mysentence);
   printf("%s\n", mysentence);

   return 0;
}

/* reverse the words in a sentence */
void reverse_words(char *sentence)
{
   char *start = sentence;
   char *end = sentence;

   /* find the end of the sentence */
   while (*end != '\0') {
      ++end;
   }
   --end;

   /* reverse the characters in the sentence */
   reverse_chars(start, end);
   
   /* reverse the characters in each word */
   while (*start != '\0') {
      /* move start pointer to the beginning of the next word */
      for (; *start != '\0' && *start == ' '; start++) ;

      /* move end pointer to the end of the next word */
      for (end=start; *end != '\0' && *end != ' '; end++) ;
      --end;

      /* reverse the characters in the word */
      reverse_chars(start, end);

      /* move to next word */
      start = ++end;
   }
}

/* reverse the characters in a string */
void reverse_chars(char *left, char *right)
{
   char temp;

   while( left < right) {
      temp = *left;
      *left = *right;
      *right = temp;
      ++left;
      --right;
   }
}

Comments


#1 Karsten Sorensen commented on :

Reposted a C version so it looks better. Just to show the power of C.

Here is a C version with better formatting:

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

int main(int argc, char *argv[])
{
  char **pstr, *ptok[20];
  int i;
  char pinstr[] = "Quick brown fox jumps over the lazy dog.";

  for (i = 0, ptok[i++] = strtok(pinstr, " "); ptok[i] = strtok(NULL, " "); i++);
  for (i--; i > -1; i--) {
    printf ("%s ", ptok[i]);
  }
}

#2 Eliot commented on :

Karsten: Thanks for you solution. I removed your first comment with the broken formatting and I added a single space to your second comment to fix the formatting.


#3 Greathbk commented on :

Python is really great and very good language. How it sorted the program in just four lines... Really python is a high level programming language but it is very very easy to learn and implement.....


#4 LB commented on :

I am trying to run this program but it keeps cutting off the first word everytime i do it. Would anyone know why?


#5 ElroySmith commented on :

Python:

a = "Quick brown fox jumps over the lazy dog."

#reverse 

b = a[::-1]

#6 Eliot commented on :

ElroySmith:
Your solution actually reverses the characters of the string and not the words.

a = "The quick brown fox jumped over the lazy dog."
b = a[::-1]
print b

Results:

.god yzal eht revo depmuj xof nworb kciuq ehT

This is a neat trick though. For others, the slicing notation used is start:end:step and a negative step indexes from the end of the list instead of the beginning. See Note 5 in the Python documentation for Sequence Types


#7 ElroySmith commented on :

Hi, You're right :)

But what will you say about this :

a = "The quick brown fox jumped over the lazy dog."

reversed order of words

b = " ".join( a.split()[::-1] )

I think it will do the trick :)

But it's the same as b = " ".join( reversed( a.split() ) )

(only you don't need to remember magic word reversed and also because in the first version there are less parenthesis it's looks more readable for me)

What do you think ? :) BR, Elroy


#8 nilesh commented on :

Three Lines of code

sentence = "The quick brown fox jumped over the lazy dog."

For Reversing string,

" ".join(sentence.split()[::-1])