I am trying to make a function to convert from prefix to infix implementation in C:

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

#define type char*   //type of element in the stack
#define max  100

typedef struct {
    int top;
    type array[max];
} stack;

stack *initialize() {
    stack *s = malloc(sizeof(stack));
    if (!s)
        return NULL;
    s->top = 0;
    return s;
}

void push(stack *s, type x) {
    s->array[s->top  ] = x;
}

type pop(stack *s) {
    return s->array[--s->top];
}

type isfull(stack *s) {
    return s->top >= max;
}

type isempty(stack *s) {
    return !s->top;
}

type peek(stack *s) {
    return s->array[s->top - 1];
}

int isoperator(char *x) {
    if (x[0] == ' ' || x[0] == '*' || x[0] == '/' || x[0] == '-' || x[0] == '^')
        return 1;
    else
        return 0;
}

void error() {
    printf("error");
    exit(-1);
} 

char *prefix_to_infix(char *pre) {
    char op1[20], op2[20], temp[2];
    char *fin = malloc(30);
    stack *s = initialize();
    int i;
    for (i = strlen(pre) - 1; i >= 0; i--) {
        temp[0] = pre[i];
        temp[1] = '\0';
        if (temp[0] == ' ')
            continue;
        if (temp[0] >= '0' && temp[0] <= '9') { 
            push(s, temp);
        } else
        if (isoperator(temp)) {
            if (!isempty(s)) {
                strcpy(op1, pop(s));
            } else
                error();
            if (!isempty(s)) {
                strcpy(op2, pop(s));
            } else
                error();
            strcpy(fin, "(");
            strcat(fin, op1);
            strcat(fin, temp);
            strcat(fin, op2);
            strcat(fin, ")");
            push(s, fin);
        }
    }
    if (isempty(s))
        error;
    strcpy(fin, pop(s));
    return fin;
}

int main() {
    char *s = prefix_to_infix("-78");
    printf("%s", s);
    return 0;
}

The output should be (7-8) but the output is (---) when I pop from the stack it gives '-' I don't know how because I only push numbers in the stack

CodePudding user response：

When you push a string with push(s, temp); or push(s, fin); only the pointer gets copied to the stack. The array it points to gets overwritten by the next token or the next string composed using strcpy and strcat.

You should allocate a copy of the string.

Here is a modified version:

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

#define STACK_SIZE 100

typedef struct {
    int top;
    char *array[STACK_SIZE];
} stack;

stack *initialize(void) {
    stack *s = malloc(sizeof(stack));
    if (!s)
        return NULL;
    s->top = 0;
    return s;
}

void push(stack *s, const char *x) {
    assert(s->top < STACK_SIZE);
    s->array[s->top  ] = strdup(x);
}

char *pop(stack *s) {
    assert(s->top > 0);
    return s->array[--s->top];
}

int isfull(const stack *s) {
    return s->top >= STACK_SIZE;
}

int isempty(const stack *s) {
    return !s->top;
}

char *peek(const stack *s) {
    assert(s->top > 0);
    return s->array[s->top - 1];
}

int isoperator(const char *x) {
    return (x[0] == ' ' || x[0] == '*' || x[0] == '/' || x[0] == '-' || x[0] == '^');
}

void error(void) {
    printf("error");
    exit(-1);
}

char *prefix_to_infix(const char *pre) {
    stack *s = initialize();
    int i = strlen(pre);
    while (i --> 0) {
        char temp[2], buf[80];
        temp[0] = pre[i];
        temp[1] = '\0';
        if (isspace((unsigned char)temp[0]))
            continue;
        if (temp[0] >= '0' && temp[0] <= '9') {
            push(s, temp);
        } else
        if (isoperator(temp)) {
            char *op1 = NULL, *op2 = NULL;
            if (!isempty(s)) {
                op1 = pop(s);
            } else {
                error();
            }
            if (!isempty(s)) {
                op2 = pop(s);
            } else {
                error();
            }
            snprintf(buf, sizeof buf, "(%s%s%s)", op1, temp, op2);
            free(op1);
            free(op2);
            push(s, buf);
        } else {
            printf("syntax error at '%s'\n", temp);
        }
    }
    if (isempty(s)) {
        error();
    }
    return pop(s);
}

int main() {
    char *s = prefix_to_infix("-78");
    printf("%s\n", s);
    free(s);
    return 0;
}