Postfix to Infix notation conversion in C

Question

I am having a problem converting from postfix to infix in C. I know where the problem is, but I don't know how to fix it.

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

struct Stack {
    int *T;
    int top;
    int capacity;
};

void dobracket(char *T, int end) {
    for (int i = end - 1; i >= 0; i--)
        T[i+1] = T[i];
    T[0] = '(';
    T[end+1] = ')';
    T[end+2] = '\0';
}

// ab+c-def^^*g/
char *postfix_to_infix(char *postfix) {
    int pos = 0;
    struct Stack Mystack;
    init_stack(&Mystack, 20);

    char *infix = (char *)malloc(sizeof(char) * strlen(postfix));
    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i]) || isalpha(postfix[i]))
            push(&Mystack, postfix[i]);
        else if (Mystack.top > 0) {
            char second = pop(&Mystack);
            char first = pop(&Mystack);
            infix[pos++] = first;
            infix[pos++] = postfix[i];
            infix[pos++] = second;
            dobracket(infix, pos);
            pos = pos + 2;
        }
        else {
            infix[pos++] = postfix[i];
            infix[pos++] = pop(&Mystack);
            dobracket(infix, pos);
            pos = pos + 2;
        }
    }
    infix[pos] = '\0';
    return infix;
}

#include <stdio.h>

int main(void) {
    char *p = postfix_to_infix("83-2*53/+");
    fputs(p,stdout);
    return 0;
}

I know I will reach until ((((8-3)*2), and then it will put 5/3)+. After that it will try pop an empty stack, but I don't know how to do it. What is the error?

I tried to convert postfix noatation 83-2*53/+ to infix. I expected (((8-3)*2) +(5/3)). The result is empty ((((8-3)*2)5/3)+�).

Answer 1

First off, your malloc() isn't nearly big enough. The infix notatation adds parentheses, and can double the length.

Second, you are not handling the case when you have an operator with nothing on the stack. Also your conditionals are wrong for the cases. In the first case when you do two pop()s, you need if (Mystack.top >= 2). The next one with one pop() should not be just else but else if (Mystack.top >= 1). Then there needs be a third case, a final else, currently missing, for an empty stack.

Third, your approach won't work, since you are losing track of where the subexpressions are. You need to rethink the approach and model it on your test case, before writing any code at all.