Reverse a sentence using stack in C

Question

i want to reverse a sentence using stack in c. eg. how are you => you are how.

i have written the following program

#include<stdio.h>
#include<conio.h>
struct rev
{
    char *var;
    struct rev *next;       
};
struct rev *top=NULL;
struct rev *temp,*test;
main()
{
    int start, j = 0;
    char *p="Hi, How are you? Hope everything is fine";
    char *s;
    char *t;
    *t = '\0';
    s = p;
    while(1) {
        if(*p == ' '|| *p == '\0') {
            printf("Inside if \n");
            *(t + j) = '\0';
            printf("This is t %s\n",t);

            if(top == NULL) {
                temp = (struct rev *)malloc(sizeof(struct rev));
                temp->next = NULL;
                temp->var=t;
                top = temp; 
            } else {
                temp = (struct rev *)malloc(sizeof(struct rev));
                printf("This is going in stack %s\n", t);
                temp->var = t;
                temp->next = top;
                top = temp;
                printf("This is top %s\n", top->var);
            }
            j = 0;         
        } else {
            *(t+j) = *p;
            printf("%c\n", *p);
            j++;    
        }   
        if(*p == '\0') {
            break;
        }

        //printf("%c",*p);              
        p++;
    }
    struct rev *show;
    show = top;
    while(show != NULL) {
        printf("%s\n", show->var);
        show = show->next;               
    }

    getch();      
}

It is storing correctly but on traverse it is giving only the final element. i am not be able to figure it out what is the problem. Here is my output window:-

enter image description here

[Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). — unwind, Feb 18 '14 at 08:59

Some programmer dude · Answer 1 · 2014-02-18T09:21:09.993

2

Read complete line. Tokenize string on whitespace, pushing each word to the stack. Pop the stack while printing.

Useful functions:

Complete solution can be done in less than 20 lines (including structure definitions, header files, etc.)

You also have a problem with undefined behavior in your code. You have a pointer p which points to a constant array of characters (all string literals are constant arrays of characters). Then you try to modify that constant array.

You might want something like this instead:

char arr[] = "Some string here";
char *p = arr;

And you have another case of undefined behavior as well: You have the pointer t which is not initialized. You then continue to dereference it. I would say that you are lucky to not get a crash.

You also don't update t in the loop, which you probably should.

edited Feb 18 '14 at 09:21

answered Feb 18 '14 at 08:59

Some programmer dude

400,186
35
402
621

I did the same thing.. I started reading the string. Upon encounter of a whitespace i pushed the word into the word into the stack.. and continued the process.. Upon reaching the end of string. I stated to pop the elements of the stack and print them.. The problem is its just printing the last (top) element of stack.. – NameNotFoundException Feb 18 '14 at 09:05
@vicky Then you're not actually popping the stack properly. – Some programmer dude Feb 18 '14 at 09:06
This is what I am asking.. I am not able to figure out the error.. hope u could help me out. Thanks – NameNotFoundException Feb 18 '14 at 09:08
@vicky Updated my answer with a pretty serious problem. – Some programmer dude Feb 18 '14 at 09:14

Deepthought · Accepted Answer · 2014-02-18T09:43:56.500

First of all your char *t is just a pointer, make it point to malloced memory and then go ahead... I dont understand how the code is even running ... You are doing *(t + j) when t is actually pointing to junk.

On first look You are overwriting t... after parsing a string. i.e you set j = 0 and overwrite previously stored string and your struct rev hold a pointer to this t hence you are getting you? you? you? as output. instead of having char *var in struct rev point to t .. your char *var point to a malloced memory and do strcpy or strtok

I just did a rough modification of your code and it worked for me on linux + gcc ... Here's the code:

#include<stdio.h>
#include <stdlib.h>
struct rev
{
    char *var;
    struct rev *next;       
};
struct rev *top=NULL;
struct rev *temp,*test;
main()
{
    int start, j = 0;
    char *p="How are you?";
    char *s;
    char *t;
    t = malloc(1000);
    if (t == NULL) {
        //OUT OF MEMORY
        exit(1);
    }
    s = p;
    while(1) {
        if(*p == ' '|| *p == '\0') {
            printf("Inside if \n");
            *(t + j) = '\0';
            printf("This is t %s\n",t);

            if(top == NULL) {
                temp = (struct rev *)malloc(sizeof(struct rev));
                temp->next = NULL;
                temp->var = malloc(100);
                if (temp->var == NULL) {
                   //OUT OF MEMORY
                   exit(1);
                }
                strcpy(temp->var, t);
                top = temp; 
            } else {
                temp = (struct rev *)malloc(sizeof(struct rev));
                printf("This is going in stack %s\n", t);
                temp->var = malloc(100);
                 if (temp->var == NULL) {
                   //OUT OF MEMORY
                   exit(1);
                }
                strcpy(temp->var, t);
                temp->next = top;
                top = temp;
                printf("This is top %s\n", top->var);
            }
            j = 0;
        } else {
            *(t+j) = *p;
            printf("%c\n", *p);
            j++;    
        }   
        if(*p == '\0') {
            break;
        }

        //printf("%c",*p);              
        p++;
    }
    struct rev *show;
    show = top;
    while(show != NULL) {
        printf("%s\n", show->var);
        show = show->next;               
    }

    //getch();      
}

Here's the output:

H
o
w
Inside if 
This is t How
a
r
e
Inside if 
This is t are
This is going in stack are
This is top are
y
o
u
?
Inside if 
This is t you?
This is going in stack you?
This is top you?
you?
are
How

PS: I dont undertand in which part of the code you are implementing push|pop ... You are using list and telling you want a stack. Stack and List are 2 different data-structures.

score 0 · Answer 3 · answered Feb 18 '14 at 09:20

0

You can start by initializing variable t to point to a valid memory address.

answered Feb 18 '14 at 09:20

barak manos

29,648
10
62
114

score 0 · Answer 4 · answered Feb 18 '14 at 09:40

0

It seems that the logic of "show" is written incorrectly-

show = top;
while(show != NULL) {
    printf("%s\n", show->var);
    show = show->next;               
}

pointing show to top and printing "show->next" is incorrect way of popping out from stack.

answered Feb 18 '14 at 09:40

nishapatel

23
4

Can you offer the Original Poster also a solution? – Roland Bär Feb 18 '14 at 10:01

score 0 · Answer 5 · answered Feb 18 '14 at 10:30

Here is an example of pop function-

int pop(STACK **head) {
if (empty(*head)) {                         
   fputs("Error: stack underflow\n", stderr);
   abort();
} else {                                    
    STACK *top = *head;
    int value = top->data;
    *head = top->next;
    free(top);
    return value;}}

Reverse a sentence using stack in C

5 Answers5