Reversing words of a sentence?

Question

I do not understand what I am doing wrong. It looks like this should work:

Calling reverse_reverse("this house is blue"); should first print out "this house is blue", then "blue is house this"..

void reverse_reverse(char * str) {
    char temp;

    size_t len = strlen(str) - 1;
    size_t i;
    size_t k = len;

    for(i = 0; i < len; i++) {
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;
        k--;

        if(k == (len / 2)) {
            break;
        }
    }

    cout << str << endl;

    i = 0;
    for(k = 0; k < len; k++) {
        if(str[k] == ' ') {
            size_t a = k;
            for(size_t b = i; b < k; b++) {
                temp = str[b];
                str[b] = str[a];
                str[a] = temp;
                a--;

                if(a == (((k - i) / 2) + i)) {
                    break;
                }
            }
        }
        i = k + 1;
    }

    cout << str << endl;
}

Can you describe exactly what's going wrong with the code? Are you getting some kind of error during compilation? Are you getting improper output at all points (or one point)? These kinds of things will help everyone answer questions a lot. — pseudoramble, Feb 08 '11 at 05:12
The basic intuition seems right. What is the program printing? Do you have any hunches as to why it doesn't work? The more details you give, the better we'll be able to help. — templatetypedef, Feb 08 '11 at 05:13
The first for loop part reverses the sentence. The second for loop part is reversing each word. — gsk, Feb 08 '11 at 05:15
possible duplicate of [Reversing words in a sentence](http://stackoverflow.com/questions/3276582/reversing-words-in-a-sentence) — leppie, Feb 08 '11 at 05:26
@leppie: This is a specific question with an _implementation_ of the solution. So this is not a dupe. In fact OP showing the working is a good thing, if it is homework. Of course OP should actually have mentioned what the output was, otherwise this question would have been worth a +1. But +1 anyway, as the code is there... — , Feb 08 '11 at 05:28
@Moron: If he mentioned the output it would have been homework :) — leppie, Feb 08 '11 at 05:57
sounds like a take-home/studying for job interview. I've been asked something similar in a couple of job interviews. — typo.pl, Feb 08 '11 at 06:04
@leppie: I don't understand these comments about homework. Homework is _not discouraged_ as long as OP shows the work (which they did)! In fact given the plenty of other homework problems we see, this is much better and so deserves a +1. — , Feb 08 '11 at 06:05
Silly close votes (and downvote to the question), IMO. Anyway... — , Feb 08 '11 at 19:17

score 5 · Answer 1 · 2011-02-08T05:36:01.787

You have

i = k+1

and then the for loop

for(size_t b = i; b < k; b++)

This will never go in as i > k before the start of the loop and thus b > k.

Perhaps you meant to have that line in the if block:

if (str[k] == ' ') {  
...

    i = k+1; // <----- Here
}
// i = k+1; // Instead of here.

I don't think that will work either, but will get you much closer to what you desire.

Jim Balter · Answer 2 · 2011-02-08T06:15:00.947

1

It would be easier to read and understand and debug your code if it were simpler. Note that you repeat code to reverse a sequence of characters in two different places -- you should use a subroutine. A simpler, more intuitive, and faster algorithm than the one you're using is

/* reverse s[first ... last] in place */
void reverse(char* s, int first, int last){
    for( ; first < last; first++, last-- ){
        char c = s[first];
        s[first] = s[last];
        s[last] = c;
    }
}

Then your program reduces to something simple:

void reverse_reverse(char* s) {
    int len = strlen(s);
    reverse(s, 0, len - 1);

    for( int word = 0, i = 0;; i++ ){
        if( i == len || s[i] == ' ' ){
            reverse(s, word, i-1);
            if( i == len ) break;
            word = i + 1;
        }
    }
}

Note that I moved the end test inside of the for loop to handle the last word in the string if it isn't followed by a space.

edited Feb 08 '11 at 06:15

answered Feb 08 '11 at 05:58

Jim Balter

16,163
3
43
66

My intuition came up with the code that I posted.. do I have any hope? – Lucas Feb 08 '11 at 06:38
Of course you do. :-) I probably shouldn't have used the word "intuitive" as that is subjective and individual, and "swap until the index gets halfway" is at least as intuitive as "swap until the first and last indices meet" ... but with experience you'll learn that the latter approach is easier and less error prone. A similar case is a binary search; novices tend to subdivide the array by repeatedly dividing its length by 2, which only works if the length is a power of 2. Better is to find the midpoint of the first and last index, which can be done recursively for any length. – Jim Balter Feb 08 '11 at 06:52
+1: I was about to suggest a refactor, but after OP tried to correct some bugs first! Anyway... – Feb 08 '11 at 07:00
Thanks for the +1. My point here was that refactoring makes it easier to reason about code; correcting bugs first would defeat the purpose of my post. And you had already posted that the assignment to i (word in my version) needed to be moved inside the loop. My addition was the need to handle the end-of-string case properly -- there was the risk the the OP would never realize that bug exists; hopefully the need to deal with such issues will now be remembered for future tasks. – Jim Balter Feb 08 '11 at 09:05
@Jim: You can use the @Moron type notification (the site supports this feature). I don't agree that fixing the bugs would defeat the purpose of your post. In fact, once they see how painful it is to find and fix bugs in the duplicated code, your post will make much more sense: they will understand the _why_ behind the refactor. Also, there are actually other bugs in the code, independent of the refactor issue and it looks like a CS101 homework problem :-) – Feb 08 '11 at 19:15
@Moron I'm aware of the notation but I'm new here and sometimes forget it. – Jim Balter Feb 09 '11 at 00:59

score 0 · Answer 3 · answered Feb 08 '11 at 06:50

0

Instead of reversing the whole string once and then each word another time, you could do something like this:

void reverse(const char *s)
{
    int e = strlen(s) - 1;
    int b = e;
    while (b) {
        while (b && s[b - 1] != ' ') 
            b--;
        int i;
        for (i = b; i <= e; ++i)
            putchar(s[i]);
        while (b && s[b - 1] == ' ') {
            printf(" ");
            b--;
        }
        e = b - 1;
    }
}

answered Feb 08 '11 at 06:50

Peyman

447
3
7

That should be called something like print_reverse, since unlike the OP's program it doesn't reverse anything. – Jim Balter Feb 08 '11 at 09:09
1

@Jim Correct; though you can easily replace `putchar` with `t[j++] = s[i]` and there you have the reverse in `t`. – Peyman Feb 08 '11 at 15:48

Reversing words of a sentence?

3 Answers3