C语言中Postfix转Infix表达式实现问题求助

核心错误原因 #

1. 栈设计完全错误：后缀转中缀时，栈需要存储子表达式字符串（比如(8-3)），而非单个字符。原代码栈内仅存单个字符，处理运算符时弹出字符拼接后，未将新生成的子表达式压回栈，导致后续操作丢失中间结果，最终触发栈空异常。
2. 缓冲区操作逻辑混乱：直接在全局infix缓冲区拼接内容，而非通过栈保存中间子表达式，导致表达式拼接顺序错误，出现多余括号和乱码。
3. 内存分配不足：中缀表达式长度远大于后缀（每个二元运算会增加2个括号），原代码按后缀长度分配内存，会触发缓冲区溢出，产生乱码。
4. 缺少栈操作实现：代码调用了init_stack、push、pop但未提供实现，这也是运行时崩溃的潜在诱因。

修复方案 #

1. 修正栈结构 #

将栈元素类型改为字符串指针，用于存储子表达式：

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

2. 实现正确的栈操作 #

void init_stack(struct Stack *stack, int capacity) {
    stack->capacity = capacity;
    stack->top = -1;
    stack->T = malloc(sizeof(char*) * capacity);
}

int push(struct Stack *stack, char *str) {
    if (stack->top >= stack->capacity - 1) return 0;
    stack->T[++stack->top] = str;
    return 1;
}

char* pop(struct Stack *stack) {
    if (stack->top < 0) return NULL;
    return stack->T[stack->top--];
}

3. 重写后缀转中缀逻辑 #

核心逻辑：

• 遇到操作数时，转为字符串压入栈
• 遇到运算符时，弹出两个子表达式，拼接为(左表达式+运算符+右表达式)，将新字符串压回栈
• 最终栈顶字符串即为完整中缀表达式

4. 完整修复代码 #

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

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

void init_stack(struct Stack *stack, int capacity) {
    stack->capacity = capacity;
    stack->top = -1;
    stack->T = malloc(sizeof(char*) * capacity);
}

int push(struct Stack *stack, char *str) {
    if (stack->top >= stack->capacity - 1) return 0;
    stack->T[++stack->top] = str;
    return 1;
}

char* pop(struct Stack *stack) {
    if (stack->top < 0) return NULL;
    return stack->T[stack->top--];
}

char *postfix_to_infix(char *postfix) {
    struct Stack Mystack;
    init_stack(&Mystack, 20);

    for (int i = 0; postfix[i] != '\0'; i++) {
        // 处理操作数
        if (isdigit(postfix[i]) || isalpha(postfix[i])) {
            char *operand = malloc(2 * sizeof(char));
            operand[0] = postfix[i];
            operand[1] = '\0';
            push(&Mystack, operand);
        }
        // 处理二元运算符
        else {
            char *right = pop(&Mystack);
            char *left = pop(&Mystack);
            if (!left || !right) {
                fprintf(stderr, "Invalid postfix expression\n");
                exit(1);
            }
            // 计算所需内存：左长度+运算符1+右长度+括号2+结束符1
            int len = strlen(left) + strlen(right) + 4;
            char *expr = malloc(len * sizeof(char));
            snprintf(expr, len, "(%s%c%s)", left, postfix[i], right);
            // 释放旧子表达式内存，避免泄漏
            free(left);
            free(right);
            push(&Mystack, expr);
        }
    }

    char *result = pop(&Mystack);
    free(Mystack.T);
    return result;
}

int main(void) {
    char *p = postfix_to_infix("83-2*53/+");
    fputs(p, stdout);
    free(p); // 释放结果内存
    return 0;
}

修复后运行结果 #

输入83-2*53/+，输出(((8-3)*2)+(5/3))，与预期一致，无栈空异常。

额外注意事项 #

• 必须手动释放动态分配的内存，避免内存泄漏
• 可添加运算符合法性判断，增强代码鲁棒性
• 栈初始容量可根据后缀表达式长度动态调整，避免溢出

内容的提问来源于stack exchange，提问作者Alaa Zaabat