中缀转后缀算法异常：全包围括号表达式末尾残留左括号

我在数据结构课程中实现中缀表达式转后缀表达式的算法，核心逻辑已完成，但遇到异常：当输入是完全被括号包围的表达式（如(2+2)）时，程序输出会多一个左括号。正确结果应为「2 2 +」，但实际输出是「2 2 + (」。其他带括号的表达式（如1/(2+3)）转换结果正常。

实现采用链式队列存储输出结果，教授提供的get_type、get_priority函数已确认无问题。我推测是某个环节误将左括号入队，初步排查问题可能出在处理右括号的代码段，但该段循环明确要求栈顶为左括号时停止，却仍出现左括号被入队的情况。

核心转换函数代码 #

QUEUE infix_to_postfix(char *infixstr) {
    char *p = infixstr;
    QUEUE queue = { 0 }; // 存储后缀表达式结果的队列
    STACK stack = { 0 }; // 辅助栈
    int sign = 1, num = 0;
    while (*p) { // 遍历表达式字符串

        if (*p == '-' && (p == infixstr || *(p - 1) == '(')) { // 获取操作数的符号
            sign = -1;
        }

        else if (get_type(*p) == 0) { // 当前字符是数字，用霍纳算法处理多位数
            num = *p - '0';
            while ((*(p + 1) >= '0' && *(p + 1) <= '9')) {
                num = num * 10 + *(p + 1) - '0';
                p++;
            }
            enqueue(&queue, new_node(sign * num, 0));
            sign = 1;
        }

        else if (get_type(*p) == 1) { // 当前字符是运算符
            int current_priority = get_priority(*p);
            while (stack.top != NULL && stack.top->data != '('
                    && current_priority <= get_priority(stack.top->data)) {
                enqueue(&queue, pop(&stack));
            }
            push(&stack, new_node(*p, 1));
        }

        else if (get_type(*p) == 2) { // 当前字符是'('
            push(&stack, new_node(*p, 2));

        }

        else if (get_type(*p) == 3) { // 当前字符是')'
            while (stack.top != NULL && stack.top->data != '(') {
                enqueue(&queue, pop(&stack));
            }

            pop(&stack);
            
        }
// 忽略其他字符
        p++; // 移动到下一个字符
    }
// 最后将栈中剩余元素弹出并入队
    while (stack.top) {
        enqueue(&queue, pop(&stack));
    }
    return queue;
}

调试定位 #

调试后发现问题至少出在处理右括号的代码段：

else if (get_type(*p) == 3) { // *p == ')'
            while (stack.top != NULL && stack.top->data != '(') {
                enqueue(&queue, pop(&stack));
            }

            pop(&stack);
            
        }

尽管循环明确在栈顶为左括号时停止，但左括号仍被入队。

补充完整代码片段 #

公共结构体与函数声明 #

typedef struct node {
    int data;
    int type;
    struct node *next;
} NODE;

NODE* new_node(int data, int type);
void clean(NODE **npp);
void display(NODE *np);
int get_type(char c);
int get_priority(char op);

显示函数实现 #

void display(NODE *np) {
    while (np) {
        if (np->type == 0)
            printf("%d", np->data);
        else
            printf("%c", np->data);

        np = np->next;

        if (np)
            printf(" ");
    }
}

队列相关定义与实现 #

typedef struct queue {
    int length;
    NODE *front;
    NODE *rear;
} QUEUE;

void enqueue(QUEUE *qp, NODE *np);
NODE* dequeue(QUEUE *qp);
void clean_queue(QUEUE *qp);

void enqueue(QUEUE *qp, NODE *np) {
// 自定义实现
    if (qp->rear == NULL) {
        qp->front = np;
        qp->rear = np;
    }

    else {
        qp->rear->next = np;
        qp->rear = np;
    }

    qp->length++;

    return;
}

栈相关定义与实现 #

void push(STACK *sp, NODE *np);
NODE* pop(STACK *sp);
void clean_stack(STACK *sp);

NODE* pop(STACK *sp) {
// 自定义实现
    NODE *return_node;

    if (sp->top == NULL) {
        return NULL;
    }

    else {
        return_node = sp->top;
        sp->top = sp->top->next;
    }

    sp->length--;

    return return_node;
}

测试代码 #

char *tests[] = { "1+2", "(1+2*3)", "1+(6/3)" };

void test_infix_to_postfix() {
    printf("------------------\n");
    printf("Test: infix_to_postfix\n\n");
    int n = sizeof tests / sizeof *tests;
    QUEUE q = { 0 };
    for (int i = 0; i < n; i++) {
        q = infix_to_postfix(tests[i]);
        printf("infix_to_postfix(%s): ", tests[i]);
        display(q.front);
        clean_queue(&q);
        printf("\n");
    }
    printf("\n");
}


int main(int argc, char *args[]) {
    if (argc <= 1) {
        test_infix_to_postfix();
        test_evaluate_postfix();
        test_evaluate_infix();
    } else {
        interative_exprssion(args[1]);
    }
    return 0;
}

问题排查与修复方案 #

核心问题推测 #

从代码逻辑看，唯一可能导致左括号入队的场景是最后弹出栈元素的循环未过滤左括号，或处理右括号时误将弹出的左括号入队（比如代码实际运行版本中把pop(&stack)写成了enqueue(&queue, pop(&stack))）。

修复步骤 #

1. 检查处理右括号的代码：确保最后一行是pop(&stack);而非enqueue(&queue, pop(&stack));，避免将左括号入队。
2. 过滤栈中剩余的左括号：修改最后弹出栈元素的循环，只将非左括号元素入队：

// 最后将栈中剩余元素弹出并入队
while (stack.top) {
    NODE *node = pop(&stack);
    if (node->data != '(') {
        enqueue(&queue, node);
    } else {
        clean(&node); // 释放左括号节点，避免内存泄漏
    }
}

3. 验证get_type函数：确保get_type('(')返回2、get_type(')')返回3，避免括号被错误归类。
4. 调试栈状态：在处理右括号的代码中加入调试输出，确认栈顶元素和弹出操作是否正常：

else if (get_type(*p) == 3) { // *p == ')'
    printf("处理右括号时，栈顶元素：%c\n", stack.top ? (char)stack.top->data : '空');
    while (stack.top != NULL && stack.top->data != '(') {
        printf("弹出运算符：%c\n", (char)stack.top->data);
        enqueue(&queue, pop(&stack));
    }
    NODE *temp = pop(&stack);
    if (temp) {
        printf("弹出左括号：%c\n", (char)temp->data);
        clean(&temp);
    } else {
        printf("栈为空，无法弹出左括号\n");
    }
}

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