Reverse words of string by recursion

Question

I'm trying to write a C function that takes a string, and return a new string with reversed words. For example, entering "How are you" should return "you are How". The following is my trial:

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

char *reverseWords(char *str, char *ac)
{
    if (!ac)
    {
        ac = malloc(strlen(str) + 1);
        ac[0] = '\0';
    }

    char *word = strtok(str, " ");
    if (!word)
    {
        return ac;
    }
    reverseWords(NULL, ac);
    strcat(ac, word);
    //strcat(ac, " ");
}

int main()
{
    char s[] = "How are you";
    char *reversed = reverseWords(s, NULL);
    printf("%s\n", reversed);
}

The previous code prints: "youareHow", so it seems that the idea is correct but just missing spaces. If I tried to uncomment the last line int the function, I don't get any output. so what's happening ? I can't understand why it didn't work.

Answer 1

I'm adding this only because sooner or later the alternative approach link I propped up on ideone.com will rot, and when it does, people may wonder wth I was talking about in general comment.

This task can be done in-place, without dynamic allocation or usage of strtok. The approach uses a technique caled reversal partitioning, and is accomplished by doing the following:

1. Locate the first whitespace from the beginning of the string to the end-marker, which is initially provided as the terminator, (but will be reduced with each recursion). If no whitespace is found in that segment, you're done.
2. Reverse the segment from the beginning of the string to, but not including the breaking whitespace discovered from (1).
3. Reverse the entire sequence from beginning to end-marker.
4. Reverse the segment from the beginning of the string to the position immediately prior to the whitespace before the moved segment.
5. Recurse using using segment not including the data just moved, nor it's leading whitespace.

That's it. now to see it with data:

step 1,2. reverse the target sequence
"abc 123 xyz" ==> "cba 123 xyz"
 ^^^               ^^^

step 3. Reverse the entire sequence
"cba 123 xyz" ==> "zyx 321 abc"

step 3 Reverse the non-target sequence, not including the trailing space
"zyx 321 abc" => "123 xyz abc"
 ^^^^^^^           ^^^^^^^

Repeat this (recursion or iteration, makes no difference) for the non-target segment, adjusting the end-marker to do so. A second walk through would look like this, noting the position of the end-marker * above the examples:

        *                *
"123 xyz abc" => "321 xyz abc"
 ^^^              ^^^

        *                *
"321 xyz abc" => "zyx 123 abc"
 ^^^^^^^          ^^^^^^^

        *                *
"zyx 123 abc" => "xyz 123 abc"
 ^^^              ^^^

Once this is done, recurse again. Now the intro looks like this:

    *
"xyz 123 abc"

but note there is no whitespace between the beginning of string and the end-marker, so we're done (and we are, in case you missed it).

---

The Code

The actual code to do this is straightforward, only the pointer math takes a few stares to fully understand. Here it is:

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

void reverse_letters(char *beg, char *end)
{
    while (beg < --end)
    {
        char tmp = *beg;
        *beg++ = *end;
        *end = tmp;
    }
}

char *reverse_words(char *beg, char *end)
{
    // find whitespace. if none then we're done.
    char *p = beg;
    for (; p != end && !isspace((unsigned char)*p); ++p);

    if (p != end)
    {
        reverse_letters(beg, p);
        reverse_letters(beg, end);
        reverse_letters(beg, beg + (end - p - 1));
        reverse_words(beg, beg + (end - p - 1));
    }

    return beg;
}

int main()
{
    char words[] = "abc 123 xyz";
    reverse_words(words, words + strlen(words));
    puts(words);
    return 0;
}

Output

xyz 123 abc

Obviously this is as tail-recursive as one can get, and therefore would be trivial to adapt to an iterative solution, which I leave as an exercise for the reader(s).

Answer 2

When you recursively call reverseWords you ignore the return code, but this is no problem as the higher level invocation already has a reference to ac.

But the highest level invocation will leave the function reverseWords at its end where you forgot to return a value.

When your program seems to work partially by printing "youareHow", you actually observed undefined behavior because the main function apparently found the address of the expected string where it expects to get the return value. As the function does not return a value, this is something left over in memory or in a register from the previously executed code.

Change your code like this:

    char *word = strtok(str, " ");
    if (!word)
    {
        return ac;
    }
    reverseWords(NULL, ac);
    strcat(ac, word);
    strcat(ac, " ");
    return ac;
}

Note that your code appends a space after every word. You can see this if you change the output as

    printf("<%s>\n", reversed);

To fix this you can replace

    strcat(ac, word);
    strcat(ac, " ");

with

    if(ac[0] != '\0')
    {
        strcat(ac, " ");
    }
    strcat(ac, word);

This will insert a space before every word if the existing string in ac is not empty.

Answer 3

You are neglecting the return value of reverseWords. I think this is ok because you have reference to ac

At the end of reverseWords function you are not returning ac which holds the contcatinated string.

Now you have to uncomment strcat(ac, " "); so that space will be added to the return value.

Now the return value will have the reversed string with spaces in it.

You forgot to free the allocated string.