Reverse the order of the words

Question

Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it

Comments

Just for the confirmation, u want if the array is "I love QueryHome" then the output should be "QueryHome love I" and space is the word separator.

Answer 1

Read one character at a time and put it in a buffer array until space is encountered in original string and then put null character at the end(to make it string) in the buffer array. Now put this buffered string in a stack. Repeat until end of original string reached. Now pop stack and copy popped string to original string one by one till the stack is not empty.

Comments

But this is a very costly method to achieve, using an extra buffer and stack..

---

Yes expensive in terms of space but very clean and understandable.
Another approach what I could think is first reverse the whole string and then reverse the order of characters in every word.

For example if initial string is "some junk string" the reversed string will be "gnirts knuj emos".
In the second step reverse letters of every word till spaces. Final string will become "string junk some";

Answer 2

See if this helps

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

#define MAX_LINE_LENGTH 1000
#define MAX_WORD_LENGTH 80

void rev(char *str) 
{
    size_t str_length = strlen(str);
    int str_idx;
    char word_buffer[MAX_WORD_LENGTH] = {0};
    int word_buffer_idx = 0;

    for (str_idx = str_length - 1; str_idx >= 0; str_idx--)
        word_buffer[word_buffer_idx++] = str[str_idx];

    memcpy(str, word_buffer, word_buffer_idx);
    str[word_buffer_idx] = '\0';
}

int main(int argc, char **argv) 
{
    char *line = NULL;
    size_t line_length;
    int line_idx;
    char word_buffer[MAX_WORD_LENGTH] = {0};
    int word_buffer_idx;

    /* set up line buffer - we cast the result of malloc() because we're using C++ */

    line = (char *) malloc (MAX_LINE_LENGTH + 1);
    if (!line) {
        fprintf(stderr, "ERROR: Could not allocate space for line buffer!\n");
        return EXIT_FAILURE;
    }

    /* read in a line of characters from standard input */

    getline(&line, &line_length, stdin);

    /* replace newline with NUL character to correctly terminate 'line' */

    for (line_idx = 0; line_idx < (int) line_length; line_idx++) {
        if (line[line_idx] == '\n') {
            line[line_idx] = '\0';
            line_length = line_idx; 
            break;
        }
    }

    /* put the reverse of a word into a buffer, else print the reverse of the word buffer if we encounter a space */

    for (line_idx = line_length - 1, word_buffer_idx = 0; line_idx >= -1; line_idx--) {
        if (line_idx == -1) 
            word_buffer[word_buffer_idx] = '\0', rev(word_buffer), fprintf(stdout, "%s\n", word_buffer);
        else if (line[line_idx] == ' ')
            word_buffer[word_buffer_idx] = '\0', rev(word_buffer), fprintf(stdout, "%s ", word_buffer), word_buffer_idx = 0;
        else
            word_buffer[word_buffer_idx++] = line[line_idx];
    }

    /* cleanup memory, to avoid leaks */

    free(line);

    return EXIT_SUCCESS;
}

Answer 3

YOUR PROBLEM ANSWER IS THIS TRY

 #include <stdio.h>
    void reverse();

    void main() {      
        printf("Please enter a sentence: ");
        reverse();
        getch();
    }    

    void reverse() {    
        char c;
        scanf("%c",&c);
        if(c != '\n') {      
            reverse();
            printf("%c",c);
    }   

}

Comments

But this is only a trick by which u can see the reverse of what you are entering, you can not reuse the code in the program.