Saltycrane logo

SaltyCrane Blog

Notes on Python, Django, and web development on Ubuntu Linux

    

How to reverse words in a sentence using Python and C

Date: 2009-04-22  |   Tags: algorithms, c_cplusplus, python   |   2 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;
   }
}

2 Comments — feed icon Comments feed for this post


#1 Karsten Sorensen commented on 2010-02-25:

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 2010-04-05:

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.

Post a comment
Required
Required, but not displayed
Optional

Format using Markdown. (No HTML.)
  • Code blocks: prefix each line by at least 4 spaces or 1 tab (and a blank line before and after)
  • Code span: surround with backticks
  • Blockquotes: prefix lines to be quoted with >
  • Links: <URL>
  • Links w/ description: [description](URL)
Created with Django | Hosted by Slicehost