当表达式全封闭时，中缀到后缀在末尾留下一个括号

Question

我正在解决数据结构课程中的一个问题，并且我已经成功地在实现算法和对核心逻辑进行排序方面完成了大部分工作。但我一直遇到的一个问题是，当被转换的表达式完全被括号包围时。例如(2+2)的情况。到后缀的正确转换是 2 2 +。但我的程序会输出 2 2 + (.

它不会对所有括号对执行此操作，仅在完全封闭表达式的独特情况下执行此操作，这意味着诸如 1/(2+3) 之类的内容就可以了

对于上下文，此实现使用链接队列来存储输出。与获取优先级或类型相关的功能是教授给我们的，应该没问题。

我现在能收集到的是，在某些时候，单独的左括号会被意外地排入队列，尽管除了最后一次清理将堆栈中剩余的所有内容排入队列之外，我看不到程序的任何部分可能会发生这种情况。但我试图调查这一点，尽管我做了什么，括号仍然存在。

请注意，我们应该假设此任务中的最佳或“完美”输入，因此缺乏考虑一些边缘情况和可能导致错误的场景

就目前而言，这就是函数

QUEUE infix_to_postfix(char *infixstr) {
    char *p = infixstr;
    QUEUE queue = { 0 }; // result postfix expression in queue
    STACK stack = { 0 }; // auxiliary stack
    int sign = 1, num = 0;
    while (*p) { // expression string traversal

        if (*p == '-' && (p == infixstr || *(p - 1) == '(')) { // get the sign of an operand
            sign = -1;
        }

        else if (get_type(*p) == 0) { // namely *p is digit character, aation: use horner’s algorithm to get the operand
            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) { // namely *p is an operator character
            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) { // *p == '(‘
            push(&stack, new_node(*p, 2));

        }

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

            pop(&stack);

        }
// else ignore
        p++; // move to next character
    }
// finally pop each node and insert it to queue
    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);
            
        }

由于某种原因，在循环中，它似乎在末尾将“(”字符排入队列，尽管循环中有明确的指示，如果堆栈顶部是左括号，则不继续进行。

编辑2：

根据要求，我添加了更多部件和主程序。

常见

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) {
// your code
    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) {
// your code
    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;
}

Answer 1

问题在于，当您使用弹出入队序列将节点从堆栈转移到队列时，转移节点的

next

字段仍然指向堆栈中的后继节点。您需要清除该

next

指针。

您可以在

enqueue

中通过添加作业来修复该问题

np->next = NULL;

push

函数不会有这个问题。尽管您没有提供该函数的代码，但很明显它会有一个像

np->next = sp->top;

这样的赋值，因此旧的

next

字段值不会像您在

enqueue

函数中那样带来严重破坏。