Using stack concept to invert words

Question

I am doing a work of Algorithms and Data Structure, which uses the concept of stack to do the inversion of words. However, when I am compiling the program, it is pointing out some errors that I do not know how to modify them.

Note: I marked errors in the program in the form of comments.

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

typedef struct cel {

char conteudo;
struct cel *prox;
} celula;

void empilha(char c, celula *topo) { /* Atenção Aqui*/

celula *nova;
nova = malloc( sizeof (celula)); /* Principal erro do programa!! */
nova->conteudo = c;
nova->prox = topo->prox;
topo->prox = nova;

}

char desempilha(celula *topo) {

char c;
celula *pt;
pt = topo->prox;
c = pt->conteudo;
topo->prox = pt->prox;
free(pt);
return c;

}

int main() {

char frase[50];
int i;
celula cabeca;
celula *topo;
topo = &cabeca; 
topo->prox = NULL;
printf("Informe a frase: ");
gets(frase); /* Possível erro aqui  ()*/
for (i=0; frase != '\0'; i++)
empilha(frase, topo); /* Talvez erro aqui ()*/
printf("\nInvertida: ");
while (topo->prox != NULL)
putchar(desempilha(topo));
putchar('\n');
return 0;

}

Answer 1

The errors that prevent the operation of your program are those:

• In place of frase != '\0' you should have used frase[i] != '\0'.

• In place of empilha(frase, topo);, you should use empilha(frase[i], topo);

However, I still make other important remarks about your code:

• It’s much easier to read, understand and find problems in a well-thought-out code.

• Never, never, under any circumstances, use the function gets. This function should never have been invented and is universally and unanimously hated by all C programmers in the world. She’s more hated than goto. Whenever you wear it gets, a demon directly from the depths of hell is summoned to the mortal plane to bring pain, curse, and torment to his program C. Even if the sea boils, if the stars fall, if the sun goes out, or if the world ends, still don’t use the function gets. The function gets was removed from the standard C language in 2011 forever and never to return. It’s too late. Use instead, fgets.

  Instead of gets(frase);, use fgets(frase, 50, stdin);.

With these changes, your program stays like this:

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

typedef struct cel {
    char conteudo;
    struct cel *prox;
} celula;

void empilha(char c, celula *topo) {
    celula *nova = malloc(sizeof(celula));
    nova->conteudo = c;
    nova->prox = topo->prox;
    topo->prox = nova;
}

char desempilha(celula *topo) {
    celula *pt = topo->prox;
    char c = pt->conteudo;
    topo->prox = pt->prox;
    free(pt);
    return c;
}

int main() {
    char frase[50];
    celula cabeca;
    celula *topo = &cabeca;
    topo->prox = NULL;
    printf("Informe a frase: ");
    fgets(frase, 50, stdin);
    for (int i = 0; frase[i] != '\0'; i++) {
        empilha(frase[i], topo);
    }
    printf("\nInvertida: ");
    while (topo->prox != NULL) {
        putchar(desempilha(topo));
    }
    putchar('\n');
    return 0;
}

See here working on ideone.

However, what you are using is not exactly a stack. The data structure you created has a head that is a special node. A stack implemented as a list simply linked, by the pure concept of defining the data structure should not have any node with special treatment different from the others. Proof of this is that topo->conteudo shall not be used and the field conteudo only makes sense from the second node. This can be solved by giving a different structure to the head, so that the code:

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

typedef struct cel {
    char conteudo;
    struct cel *prox;
} celula;

typedef struct pilha {
    struct cel *cabeca;
} pilha;

void empilha(char c, pilha *p) {
    celula *nova = malloc(sizeof(celula));
    nova->conteudo = c;
    nova->prox = p->cabeca;
    p->cabeca = nova;
}

char desempilha(pilha *p) {
    celula *pt = p->cabeca;
    char c = pt->conteudo;
    p->cabeca = pt->prox;
    free(pt);
    return c;
}

int main() {
    char frase[50];
    pilha p;
    p.cabeca = NULL;
    printf("Informe a frase: ");
    fgets(frase, 50, stdin);
    for (int i = 0; frase[i] != '\0'; i++) {
        empilha(frase[i], &p);
    }
    printf("\nInvertida: ");
    while (p.cabeca != NULL) {
        putchar(desempilha(&p));
    }
    putchar('\n');
    return 0;
}

See here working on ideone.

Finally, note that C++ is a little more demanding than C in relation to Casts, so that:

celula *nova = malloc(sizeof(celula));

C++ should look like this:

celula *nova = (celula *) malloc(sizeof(celula));

And considering that you just want to reverse the words, but not their order in the sentence, you will then need one more loop. Your code looks like this:

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

typedef struct cel {
    char conteudo;
    struct cel *prox;
} celula;

typedef struct pilha {
    struct cel *cabeca;
} pilha;

void empilha(char c, pilha *p) {
    celula *nova = (celula *) malloc(sizeof(celula));
    nova->conteudo = c;
    nova->prox = p->cabeca;
    p->cabeca = nova;
}

char desempilha(pilha *p) {
    celula *pt = p->cabeca;
    char c = pt->conteudo;
    p->cabeca = pt->prox;
    free(pt);
    return c;
}

int main() {
    char frase[50];
    pilha p;
    p.cabeca = NULL;
    printf("Informe a frase: ");
    fgets(frase, 50, stdin);
    printf("\nInvertida: ");
    for (int i = 0; frase[i] != '\0'; i++) {
        for (; frase[i] != '\0' && frase[i] != ' '; i++) {
            empilha(frase[i], &p);
        }
        while (p.cabeca != NULL) {
            putchar(desempilha(&p));
        }
        putchar(frase[i] == ' ' ? ' ' : '\n');
    }
    return 0;
}

See here working on ideone.