我正在尝试制作一个函数以在 C 中从前缀转换为中缀实现

Question

我正在尝试在 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] = '[=10=]';
        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;
}

输出应该是 (7-8) 但输出是 (---) 当我从堆栈中弹出时，它会给出 '-' 我不知道怎么做，因为我只将数字压入堆栈

Answer 1

当您使用 push(s, temp); 或 push(s, fin); 压入字符串时，只有指针被复制到堆栈。它指向的数组被下一个标记或使用 strcpy 和 strcat.

组成的下一个字符串覆盖

您应该分配字符串的副本。

这是修改后的版本：

#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] = '[=10=]';
        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;
}

我正在尝试制作一个函数以在 C 中从前缀转换为中缀实现

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

arrays

c

stack

prefix

infix-notation