Reversing order of strings

Question

This is a c program to reverse the order of words in a sentence(using stacks) read as input, but all I can get is the reverse of the each word in the sentence. How can I reverse the sentence(separated with ' ' or ',')?

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

// A structure to represent a stack
struct Stack
{
    int top;
    unsigned capacity;
    char* array;
};

struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (char*) malloc(stack->capacity * sizeof(char));
    return stack;
}


int isFull(struct Stack* stack)
{   return stack->top == stack->capacity - 1; }

// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{   return stack->top == -1;  }

// Function to add an item to stack.  It increases top by 1
void push(struct Stack* stack, char item)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
}

char pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return 0;
    return stack->array[stack->top--];
}

// A stack based function to reverese a string
void reverse(char str[])
{
    int n = strlen(str);
    struct Stack* stack = createStack(n);

    // Push all characters of string to stack
    int i;
    for (i = 0; i < n; i++)
        push(stack, str[i]);

    for (i = 0; i < n; i++)

        str[i] = pop(stack);
}

int main()
{
    char str[50];
    fgets(str, sizeof(str), stdin);
    str[strlen(str)-1]='\0';


    reverse(str);
    printf("Reversed string is %s", str);

    return 0;
}

You'll probably want to tokenize the input. Have a look at `strtok()`. — EOF, Mar 01 '16 at 00:51
Your code looks good so far, but now you need to insulate words in the input and use your reverse function on each of them. To split the input, you can use `strtok` or do a "manual" search for separators (anything that is not a letter and/or number, for instance). — kuroi neko, Mar 01 '16 at 00:57
You seems to reverse everything without regard to words. I see you `#include ` so I suggest you explore the use of `strtok` to separate each word. — Weather Vane, Mar 01 '16 at 01:08
Your stack will store the *pointer* to each word acquired by `strtok` — Weather Vane, Mar 01 '16 at 01:11
Even if I separate them, it still prints the characters of the separated words reversed. — B.am, Mar 01 '16 at 01:11
Show us your code that does the separation, then. There must be some ordering mishap somewhere. — kuroi neko, Mar 01 '16 at 01:44
Detail: `str[strlen(str)-1]='\0';` is a hackers exploit as `fgets()` can return `str[0] == 0`. Suggest http://stackoverflow.com/q/2693776/2410359 — chux - Reinstate Monica, Mar 01 '16 at 02:27
for ease of readability and understanding, please follow the axiom: *only one statement per line and (at most) one variable declaration per statement.* — user3629249, Mar 01 '16 at 15:38
please post a sample input, the actual output, and the expected output, so we have a clear understanding of the problem. — user3629249, Mar 01 '16 at 15:40
this line: `str[strlen(str)-1]='\0';` is making some (not necessarily valid) assumptions about the input string. Suggest: `char *newline; if( NULL != (newline = strstr( str, "\n") ) ) { *newline = '\0'; }` — user3629249, Mar 01 '16 at 15:44

score 0 · Accepted Answer · answered Mar 01 '16 at 02:52

Try this code

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

// A structure to represent a stack

struct Stack
{
    int top;
    unsigned capacity;
    //char* array;
    char** array;
};

struct Stack* createStack(unsigned capacity)
{
    if( capacity < 1 )
    {
        capacity = 1;
    }
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (char**) malloc(stack->capacity * sizeof(char*));
    return stack;
}



void resizeStack( struct Stack* stack , int new_size ) 
{
    if( NULL != stack && new_size > stack->capacity )  // Only support expansion 
    {
        char ** old_array = stack->array ;
        stack->array = (char**) malloc(new_size * sizeof(char*));
        memcpy(stack->array,old_array,stack->capacity * sizeof(char*));
        free(old_array);
        stack->capacity = new_size ;
    }
}
int isFull(struct Stack* stack)
{   return stack->top == stack->capacity - 1; }

// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{   return stack->top == -1;  }


// Function to add an item to stack.  It increases top by 1
void push(struct Stack* stack, char *item)
{
    if ( isFull(stack) )
    {
        resizeStack(stack, stack->capacity * 2 );
    }
    stack->array[++stack->top] =(char *) malloc(sizeof(char)*(strlen(item) +1));

    strcpy(stack->array[stack->top] , item);
}

char * pop(struct Stack* stack)
{
    char * ret = NULL;
    if(! isEmpty(stack) )
    {
        ret = stack->array[stack->top];
        stack->array[stack->top] = NULL ;
        stack->top --;
    }
    return ret;
}

void freeStack(struct Stack* stack)
{
    if( NULL != stack && NULL != stack->array ) 
    {
        while( ! isEmpty(stack) ) 
        {
           free(pop(stack));
        }
        free(stack->array);
    }
    else 
    {
        printf(" freeStack try to free NULL ");
    }
}

#define SEPARATER ' '

// A stack based function to reverese a string
void reverse(char str[])
{
    int n = strlen(str);
    struct Stack* stack = createStack(4);
    char sep[2];
    sep[0] = SEPARATER;
    sep[1] = 0 ;
    char * pch = strtok(str,sep);
    while( NULL != pch )
    {
        push(stack,pch);
        pch = strtok(NULL,sep); 
    }

    char * swap_buff = (char*)malloc((n+1) * sizeof(char));
    char * cp_buff = swap_buff;
    do
    {
        char * top = pop(stack);
        strcpy(cp_buff , top);
        cp_buff += strlen(top);
        *cp_buff++ = SEPARATER;

    }while( ! isEmpty(stack) );
    swap_buff[n] = 0;
    strcpy(str,swap_buff);
    freeStack(stack);
}

int main()
{
    char str[50];
    fgets(str, sizeof(str), stdin);
    str[strlen(str)-1]='\0';

    reverse(str);
    printf("Reversed string is %s\n", str);

    return 0;
}

Reversing order of strings

1 Answers1