2
\$\begingroup\$

I have been working on a problem that asks me to a write recursive function that can reverse the words in a string. For example if the string is "cat is running", then the result should be "running is cat".

I already completed the problem, but I feel like my implementation is really bad. Does anyone know any other way to solve this problem? Are there other ways to improve my code?

#include <stdio.h>
#include <string.h>
void reverse(char* string, int count);

int main()
{
   char string[] = "cat is running";

   //result will be running is cat

   reverse(string, -1);
   printf("%s\n", string);
}


void reverse(char* string, int count) {
   if (count == 0) {
       return;
   }

   int first = 0;
   int second = 0;
   int length = 0;

   for (int i = 0; i < strlen(string); i++) {
       if(string[i] == ' ' && first == 0) {
           first = i;
           length++;
           if (length == count) {
              break;
           }
       } else if(string[i] == ' ') {
           second = first+1;
           first = i;
           length++;
           if (length == count) {
               break;
           }
       }
   }


   if(first == 0 && second == 0) {
       return;
   }
   int flag = 0;
    for(int i = first; i >= 0; i--) {
       char temp = string[i];
       for(int k = i; k < strlen(string) - 1; k++) {
           if(flag > 2 && k == (strlen(string) - flag)) {
               k = strlen(string);
           } else {
               string[k] = string[k+1];
           }
        }
    if(i == second) {
        i = 0;
    }
    if (flag == 0) {
        string[(strlen(string) - 1) - flag] = temp;
        flag++;
    } else {
        string[(strlen(string) - flag)] = temp;
        flag++;
    }
}

count = length;
reverse(string, count - 1);
}
\$\endgroup\$

migrated from stackoverflow.com Jun 17 '16 at 11:48

This question came from our site for professional and enthusiast programmers.

  • 3
    \$\begingroup\$ The repeated calls to strlen(string) seem inefficient. Some of those calls a compiler may optimize and avoid re-calling, but not all of them. \$\endgroup\$ – chux Jun 16 '16 at 22:15
  • \$\begingroup\$ You might want to explain why you feel that your implementation is really bad. If there is anything specific you know is bad (performance? security? maybe it fails sometimes?), please specify it. Otherwise, people will have to guess - not good. \$\endgroup\$ – anatolyg Jun 16 '16 at 22:17
  • \$\begingroup\$ First thing: it is too large. Second: functions are you friends. third: a subproblem of this assignment is detecting word boundaries. \$\endgroup\$ – wildplasser Jun 16 '16 at 22:20
  • \$\begingroup\$ What are your constraints? Does the function have to be recursive? Do you have to do the reverse "in-place" [or can you use additional temp buffers]? \$\endgroup\$ – Craig Estey Jun 16 '16 at 22:20
  • \$\begingroup\$ Related: stackoverflow.com/questions/15390846/… \$\endgroup\$ – jxh Jun 16 '16 at 22:53
2
\$\begingroup\$

There is really no need to complicate matters. Keep it as simple as possible.

All you need is to track the word delimiter, in your case it is space and of course the null byte.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *reverse(char *string) {
    char *delim=string;
    while(*delim && *delim!=' '){++delim;}; // <-- this makes delim point to the next word
    if(*delim){  // <-- do this block only if there a next word
        char *retval=malloc(strlen(string)+1);
        *(delim++)='\0';
        char *temp=reverse(delim);
        sprintf(retval, "%s %s", temp, string); // <-- move the first word to the end of the sentence
        free(temp);  // <--  release the temporary storage to avoid serious memory leak
        return retval; // <-- return the newly constructed sentence
    }
    return strdup(string);  // <-- for all others return a copy of the only word or a copy of an empty string.
}
int main(int argc, char *argv[]){
    char sentence[] = "cat is running";
    char *a = reverse(sentence);
    printf("'%s'\n",a);
    free(a);
    return 0;
}

Notice the line sprintf(retval,"%s %s", reverse(delim),string);? This line will print the string returned by the recursive call to reverse() containing the remaining words in reverse and the first word into retval which is then returned to the previous caller.

\$\endgroup\$
  • \$\begingroup\$ 1) A major problem with this is that the return value needs to be compared to passed value to know if it should be free() or not. IMO, it would be better for this code to strdup(string) instead of returning string. 2) if(*string) { not needed. \$\endgroup\$ – chux Jun 18 '16 at 1:41
  • \$\begingroup\$ I totally agree @chux. I whipped this while on a lunch break. But now that this has been migrated here, I should make it bug free. \$\endgroup\$ – alvits Jun 18 '16 at 2:21
  • \$\begingroup\$ Note that strdup() is a platform-defined function and not standard C; note also that where it exists, it may return a null pointer, and calling code must check the result before dereferencing it. That last point is also true for malloc(), of course! This version seems needlessly fragile. \$\endgroup\$ – Toby Speight Oct 22 '18 at 12:47
4
\$\begingroup\$

The program below is just for fun.

Since the program asks for recursion, then in principle, recursion should be the sole iteration technique. Assuming that the requirement is to only implement a single function, and that string is '\0' terminated, the following program illustrates how this is possible.

Basically, the technique is to use the value of count control the mode of the reverse function. There are three modes: initial call, reverse each word, and reverse string.

A positive count signals the initial call, and count represents the length of the string. On initial call, the program follows the algorithm recipe of: first reverse the input string, then reverse each word in the input string.

A count value of zero causes the function to find the beginning and end of the first word in the string, reverse it, and recursively repeat the process beginning after the just reversed word.

A negative count causes the function to reverse the string assuming its length is -(count + 1). The off by one length is used to make sure the string reversal case does not run into the word reversal case. Thus, a -1 count represents an empty string.

void reverse (char *string, int count) {
    if (string == NULL || *string == '\0') return;
    // positive count := initial call
    if (count > 0) {
        reverse(string, -count-1); // reverse the whole string
        reverse(string, 0);        // reverse each word in whole string
        return;
    }
    // zero count := reverse each word in the string
    // skip over whitespace, then find end of word, reverse word, repeat
    if (count == 0) {
        char *p = string;
        int sl = strspn(p, " \t");
        int wl = strcspn(p + sl, " \t");
        reverse(p + sl, -wl-1);    // reverse the found word
        reverse(p + sl + wl, 0);   // reverse each word in rest of string
        return;
    }
    // negative count := reverse string of length -(count + 1)
    // reverse the string by swapping first and last, then shrink
    count = -(count + 1);          // fix-up count value
    if (count < 2) return;
    char t = string[0];
    string[0] = string[count-1];
    string[count-1] = t;
    reverse(++string, ---count);
}

Note the lack of looping structures within the function. All loops are accomplished with recursion or hidden by standard library functions strspn and strcspn.

\$\endgroup\$
3
\$\begingroup\$

When programming in general, C in particular, the most important quality is quite often program performance. As in execution speed and memory use. It is therefore very important to actually know what makes an efficient program and what makes an inefficient program. Inefficient == bad.

Some examples of inefficient programming:

  • Iterating over the same data multiple times.
  • Calling functions with the same or nearly the same data multiple times.
  • Using recursion.

You should avoid all of these like the plague! Now, I know your specification says "use recursion". So what a professional would do first of all, is to question if the specification makes sense. In this case it doesn't - there is absolutely no need to use recursion here.

Others have given you diverse ways of solving this with recursion. Here is an alternative approach which is efficient, instead of needlessly inefficient.


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


void reverse_words (size_t str_length, 
                    char dest [static str_length+1], 
                    const char src [str_length+1])
{
  size_t word_length;
  const char* word_end = src + str_length;       // point 1 character past last word
  char* dest_ptr = dest;
  for(const char* src_ptr = word_end-1; src_ptr > src; src_ptr--)
  {
    if(*src_ptr == ' ')
    {
      word_length = (size_t)(word_end - src_ptr - 1);
      memcpy(dest_ptr, src_ptr+1, word_length);
      dest_ptr += word_length;

      *dest_ptr = ' ';
      dest_ptr++;

      word_end = src_ptr;
    }
  }

  // special case, last word
  word_length = (size_t)(word_end - src);
  memcpy(dest_ptr, src, word_length);
  dest[str_length] = '\0';
}

int main()
{
  const char str_cat [] = "cat is running";
  char str_reverse [sizeof(str_cat)];
  reverse_words(sizeof(str_cat)-1, str_reverse, str_cat);
  puts(str_reverse);

  const char str_one [] = "oneword";
  reverse_words(sizeof(str_one)-1, str_reverse, str_one);
  puts(str_reverse);

  return 0;
}

Explanation:

  • The first thing you need to consider when designing this algorithm is if you need to reverse the string "in place" or make a reversed copy of it. The former might be more efficient, but the latter probably makes the most sense. It is usually good programming practice to treat strings as immutable.

    Depending on which method you pick, you end up with entirely different algorithms. I chose to make a copy of the original string.

  • The function takes advantage of VLAs, so that you can give two arrays of any length as input. The arrays will of course decay into pointers to the first element. But it is often preferable to use array type in function parameters over pointer type: it gives self-documenting code and also better type safety if you use external static analysis tools to check your code.

  • The static array length means that the dest parameter is guaranteed to be at least str_length+1 characters long. This makes the function slightly more flexible and ever so slightly faster (because the compiler can do a few more micro optimizations).

  • The algorithm itself iterates over the source string from the end towards the beginning. This makes it easier to pick out the words in reverse order, without the need of temporary buffers. So there is one pointer to keep track of where we are in the destination string and one to keep track of where we are in the source string (used as loop iterator).

  • The algorithm keep tracks of the end of the last found word. It is custom to design "end" pointers so that they point 1 past the end of the buffer. It could as well point at the last character in the last found word, for a slightly different algorithm. Doesn't matter.

  • Whenever finding a space, the algorithm uses memcpy to effectively copy the whole word. Note that memcpy is much more efficient than byte-by-byte copy on most CPUs, since it can grab whole chunks of data at once.

  • After copying, the algorithm manually inserts a space in the destination string.

  • Reaching the beginning of the string is a special case: there won't be no space there, but when we reach the beginning there will always be a word to copy. So this is handled separately. This is also the reason why the loop iterates to src_ptr > src rather than src_ptr >= src. (As a side note, it is questionable/poorly-defined practice to point one past the beginning of an array in C, as opposed to pointing one past the end.)

  • Finally, the new string has to be null terminated.

Unlike any code using recursion, this code is efficient. Feel free to benchmark against the recursion versions and note the vast improvement in speed and memory consumption.


( please note that naming a variable "str_cat" is very bad practice, I just couldn't resist sneaking in a C programming joke :) )

\$\endgroup\$
  • \$\begingroup\$ Nice use of char dest [static str_length+1]. 1) Code does have some issues should str_length==0, like src_ptr = word_end-1, but not too hard to solve. 2) Unclear why the cast in memcpy((void*)dest_ptr, src_ptr+1, word_length)? \$\endgroup\$ – chux Jun 18 '16 at 1:57
  • \$\begingroup\$ @chux The use of string length 0 would have to be documented, it is a matter if that's a responsibility of the caller or the function to handle. The cast is superfluous, not sure why it is there indeed, I'll remove it. \$\endgroup\$ – Lundin Jun 20 '16 at 6:57
0
\$\begingroup\$

How about checking for a " " and then substring accordingly? Just for kicks; I did this in Java without a split and a reverse function. Perhaps, the same logic could be applied in C :)

private static String rev(String in) { 
    if(in.indexOf(" ") != -1) 
    { 
        int space = in.indexOf(" "); 
        StringBuilder st = new StringBuilder(in.substring(space+1)); 
        return rev(st.toString()) + " " + in.substring(0, space); 
    } 
    else 
    { 
        return in; 
    } 
}
\$\endgroup\$
  • 2
    \$\begingroup\$ The OP asked review on a C source, so your response is a bit offtopic \$\endgroup\$ – Calak Oct 22 '18 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.