Segmentation fault in postfix to infix C code

Question

I'm writing a code to convert postfix to infix. but when i try to print the stack elements to check it it's not showing any thing. in the push function it prints the top element, but the display function only shows the top element no matter what. and there is segmentation fault after the line strcat(nn,y).The input i tried was 09+.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 20

char *stk[MAX], a[MAX];
int t = -1;

void push(char x[]);
void pop();
void display();

int main()
{
    int i = 0;

    char *x, *y, nn[MAX];
    printf("enter expression:");
    gets(a);

    while (a[i] != '\0')
    {
        if (isdigit(a[i]))
        {
            push((char [2]){ a[i], '\0' });
        }
        else
        {
            display();
            pop();
            x = stk[t];

            pop();
            y = stk[t];

            strcpy(nn, "");
            strcat(nn, "(");
            strcat(nn, y);
            strcat(nn, (char [2]){ a[i], '\0' });
            strcat(nn, x);
            strcat(nn, ")");

            push(nn);

        }

        i++;
    }

    printf("%s", stk[0]);
}

void push(char x[])
{
    t = t + 1;
    stk[t] = x;
    printf("curtop %d:%s\n", t, stk[t]);
}

void pop()
{
    t = t - 1;
}

void display()
{
    printf("%s:%s", stk[t], stk[t - 1]);
}

Answer 1

I will reiterate the comments, with some references, and add a few thoughts of my own.

The first thing you should do is read Why is the gets function so dangerous that it should not be used? gets was removed from language in C11, any halfway modern tool chain should not include it:

example.c:5:9: warning: implicit declaration of function ‘gets’; did you mean ‘fgets’? [-Wimplicit-function-declaration]

fgets is the suggested replacement. Use it.

---

Both compound literals

(char [2]){ a[i], '\0' }

occur at block scope, and thus have automatic storage duration. This means the lifetime of each object ends when their respective enclosing blocks end.

As such, you are pushing a soon-to-be dangling pointer on to the stack.

This is an example of Undefined Behaviour.

The following

push(nn);

repeatedly pushes the same pointer to the first element of nn on to the stack. This pointer value is always the same, and always points to the current contents of the array, which is constantly being changed.

Both these problems are solved by using dynamic memory to create copies of the strings pushed on to the stack.

---

nn (infix expression buffer) has the same size as a (postfix expression buffer), with both being much too small.

Remembering that to store a string in a buffer, the size of the buffer must be at least the length of the string plus one (for the null terminating byte).

The postfix expression

09+6+10*+63-/

has a string length of 13, which fits in a. With your parenthesis rules, this creates the infix expression

((((0+9)+6)+(1*0))/(6-3))

which has a string length of 25. This does not fit in nn, and strcat does nothing to guard against buffer overflows.

This would be another example of Undefined Behaviour.

---

As a quick point of design

pop();
x = stk[t];

is clumsy.

While the use of file scope variables (globals) and functions that wrap around them is a very common way data structures are introduced to beginners, you should still aim to implement something closer to an abstract data type.

pop should return the topmost element of the stack, and you as a user of the pop function should not care how that is managed, just that it behaves as expected.

char *x = pop();

The next step is to remove the file scope variables, so that more than one stack can exist in your programs at the same time.

---

Here is a cursory example program that addresses most of the issues discussed. Note that it parses input slightly differently, using whitespace as a delimiter. It follows your rules for parenthesis.

It does not validate operands or the resulting expression. Operands can be longer than a single character.

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

#define BUF_SIZE 256
#define SEP " \r\n"
#define STACK_INIT { 0 }
#define STACK_MAX 64

struct stack {
    size_t height;
    char *data[STACK_MAX];
};

size_t count(struct stack *s)
{
    return s->height;
}

int push(struct stack *s, const char *item)
{
    if (s->height >= STACK_MAX)
        return 0;

    char *copy = malloc(1 + strlen(item));

    if (!copy)
        return 0;

    strcpy(copy, item);
    s->data[s->height++] = copy;

    return 1;
}

char *pop(struct stack *s)
{
    return s->height ? s->data[--s->height] : NULL;
}

void free_stack(struct stack *s)
{
    char *item;

    while ((item = pop(s)))
        free(item);
}

int main(void)
{
    char buffer[BUF_SIZE];
    printf("enter expression: ");
    fflush(stdout);

    if (!fgets(buffer, sizeof buffer, stdin)) {
        if (ferror(stdin))
            perror("reading stdin");

        return EXIT_FAILURE;
    }

    struct stack tokens = STACK_INIT;
    char *tok = strtok(buffer, SEP);

    while (tok) {
        char expr[BUF_SIZE * 2];
        /* is the first and only character an operator? */
        int is_op = strchr("+-/*", *tok) && !tok[1];

        if (is_op) {
            if (count(&tokens) < 2) {
                fprintf(stderr, "Operator (%c) needs two operands.\n", *tok);
                free_stack(&tokens);
                return EXIT_FAILURE;
            }

            char *rhs = pop(&tokens);
            char *lhs = pop(&tokens);

            if (snprintf(expr, sizeof expr, "(%s %c %s)", lhs, *tok, rhs) >= sizeof expr)
                fprintf(stderr, "Warning: expression truncated.\n");

            free(rhs);
            free(lhs);
        }

        if (!push(&tokens, is_op ? expr : tok)) {
            fprintf(stderr, "Failed to push stack item.\n");
            free_stack(&tokens);
            return EXIT_FAILURE;
        }

        tok = strtok(NULL, SEP);
    }

    for (char *s; (s = pop(&tokens)); free(s))
        printf("%s\n", s);
}