CODEWITHSUNDEEP
cstringalgorithm
Bharat
Bharat

Reputation: 3000

Bug in my C code to reverse words in a string

I was practicing some programming problems and tried to code the popular "reverse words in a string" problem.

I tried to come up with my own code in C. I am able to partially get it right. That is, "hello world" becomes "world olleh". I am wondering what the bug is here. I think somewhere I am creating an off by 1 bug.

As much as possible, I wanted to do it without using library functions. I searched here for this problem & found many solutions, but I'd like to know why my solution doesn't work.

Here is the code:

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

void reverse(char*, int);

int main(int argc, char **argv)
{
    char st[]= "hello world";
    int len = strlen(st);
    int i=0,j=0;

    reverse(st,len-1); // Reverse the entire string. hello world => dlrow olleh

    while(st[j]){ //Loop till end of the string
        if ( *(st+j) == ' ' || *(st+j) == '\0' ) { //if you hit a blank space or the end of the string
            reverse(st+i,j-1); // reverse the string starting at position i till position before the blank space i.e j-1
            i=++j; //new i & j are 1 position to the right of old j
        }
        else {
            j++; //if a chacacter is found, move to next position
        }               
    }       

    printf("%s",st);
    return 0;
}

void reverse(char *s, int n)
{
    char *end = s+n; //end is a pointer to an address which is n addresses from the starting address
    char tmp;
    while (end>s)  //perform swap
    {
        tmp = *end;
        *end = *s;
        *s = tmp;
        end--;
        s++;
    }
}

Thank you!

UPDATE: Based on @Daniel Fischer's answer, here is the correct implementation : http://ideone.com/TYw1k

Upvotes: 3

Views: 809

Answers (4)

Nathan
Nathan

Reputation: 672

@RBK: You first take a string, reverse it, then based on specific words you again reverse them. I followed a slightly different approach of doing this. I take the string then reverse if required otherwise i copy the same word as it is. 

int main(int argc, char*argv[])
{
    char *p,st[]= "hello world";
    char buf[12]={0};
    char fstr[12]={0};
    int i=0,j=0,k=0,l=0;

    for(p=st;*p!='\0';p++){

        //Get the Word
        buf[i++] = *p;

        //Parse the Word    
        if(*p == ' ' || *(p+1) == '\0'){

            buf[i]='\0';
            j=i-1;
            i=0;        //reset counter

            if(k){      //reverse word and copy

                while(j>=i){

                    fstr[l++]=buf[j--];

                }               

                k=0;        

            }
            else{       //copy same word

                while(i<=j){

                    fstr[l++]=buf[i++];                     

                }

                i=0;    //reset counter
                k=1;

            }

        }

    }   

    fstr[l]='\0';
    printf("%s\n",fstr);
    return 0;
}

Upvotes: 0

saxi
saxi

Reputation: 419

I think that you want to reverse words in a string, not reverse the whole string and then rereverse single words. So, delete first reverse and then apply suggested changes above.

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

void reverse(char*, int);

int main(int argc, char **argv)
{
  char st[]= "hello world";
  int i=0, j=0;

  while(st[j]){ //Loop till end of the string
    if ( st[j] == ' ') { //if you hit a blank space or the end of the string
      reverse(&st[i], j - i - 1); // reverse the string starting at position i till position before the blank space i.e j-1
      i = ++j; //new i & j are 1 position to the right of old j
    }
    else {
      j++; //if a chacacter is found, move to next position
    }               
  }
  reverse(&st[i], j - i - 1);


  printf("%s\n",st);
  return 0;
}

void reverse(char *s, int n)
{
  char *end = s + n; //end is a pointer to an address which is n addresses from the    starting address
  char tmp;

  while (end > s)  //perform swap
  {
    tmp = *end;
    *end = *s;
    *s = tmp;
    end--;
    s++;
  }
}

Take care when input string would be '\0' or something like ' Hello world'. Above code doesn't managed this kind of situations. Think about it!

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726559

You have an off by one error indeed: the call

reverse(st+i,j-1);

should be

reverse(st+i,j-i-1);

Your code passes j-1 which is the length from the beginning of the string to the position of the last space; it should be the length of the last word, so you need to subtract the index of the first character (i.e. i).

You are also not reversing the last word (see the other answer for the details on that).

Upvotes: 3

Daniel Fischer
Daniel Fischer

Reputation: 183878

The problem is that

while(st[j]){ //Loop till end of the string
    if ( *(st+j) == ' ' || *(st+j) == '\0' )

the while condition prevents the loop being entered at the end of the string, so the last word doesn't get reversed again.

You can either make it an infinite loop, and add an

if (st[j] == '\0') break;

after the reversing, or reverse the last word after the while loop was left.

Upvotes: 3

Related Questions