c - 基于链表的 Infix 计算器中的错误

Question

我正在编写一个中缀计算器，它执行 5*(2+1) 等运算。我的代码中有一个我无法识别的错误。我写了一个最小的代码来展示这个问题:

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

struct x{
    double value;
    char op;
    struct x *next;
};

void add_item(struct x **ptr, double data);
void multiply (struct x *head, struct x *end);
void add (struct x *head, struct x *end);
void calculate (struct x *head, struct x *end);
void del(struct x *head);

int main()
{
    struct x *head = NULL;
    struct x **end;

    add_item(&head, 5);
    head->op = '*';

    end = &head; /*I keep track of the node after which parenthesis are entered*/

    add_item(&head, 2);

    head->op = '+';

    add_item(&head, 1);

    calculate(head, *end); /*calculate operations within parenthesis: 2+1*/
    calculate(head, NULL); /* calculate the remaining operations 5*3 */

    printf("%lf", head->value); /*This should print the overall result 15 instead of 3*/
    free(head);

    return 0;
}

void add_item(struct x **ptr, double data)
{
        struct x *item = malloc(sizeof *item);

        item->value = data;
        item->next = *ptr;
        item->op = '?';
        *ptr = item;
}

void calculate (struct x *head, struct x *end)
{  
    multiply(head, end);
    add(head, end);
}

void multiply (struct x *head, struct x *end)
{
    double result;

    if (head == end)
        return;

    if (head->next != end) {
        if ((head->next)->op == '*') {
            result = (head->next)->value * head->value;
            head->value = result;
            del(head);
            multiply(head, end);
        }

        else
            add(head->next, end);
    }
}


void add (struct x *head, struct x *end)
{

    double result;

    if (head == end)
        return;

    if (head->next != end) {
        if ((head->next)->op == '+') {
            result = (head->next)->value + head->value;
            head->value = result;
            del(head);
            add(head, end);
        }

        else
            add(head->next, end);
    }
}

void del (struct x *before_del)
{
    struct x *temp;
    temp = before_del->next;
    before_del->next = temp->next;
    free(temp);
}

代码生成一个这样的链表:1->2->5->NULL通过第一次调用calculate(head, *end);，程序可以正确执行括号内的运算并得到3作为结果。此时的列表应该是 3->5->NULL。 但是应该执行 5*3 的 calculate(head, NULL); 失败了。指向指针的 end 指针充当括号所在节点的指示符。在此示例中，节点包含值 5。如果我有表达式1+1+2*(5*3)，那么end应该指向包含值2的节点。

Answer 1

通过编写end = &head，end始终指向栈顶。您打算执行 end = head (适本地重新声明 end。这里有一些似乎有效的编辑:(我说“似乎”，因为虽然这printf 15，我真的质疑 end 指针的逻辑。使 add 和 multiply 递归似乎不太可能工作)

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

struct x {
        double value;
        void (*op)(struct x *,struct x *);
        struct x *next;
};

void add_item(struct x **ptr, double data);
void multiply (struct x *head, struct x *end);
void add (struct x *head, struct x *end);
void del(struct x *head);

int
main(void)
{
        struct x *head = NULL;
        struct x *end;

        add_item(&head, 5);
        head->op = multiply;

        end = head;
        add_item(&head, 2);

        head->op = add;
        add_item(&head, 1);

        head->next->op(head, end); /*calculate operations within parenthesis: 2+1*/
        head->next->op(head, NULL); /* calculate the remaining operations 5*3 */

        printf("%lf\n", head->value); /*This should print the overall result 15 instead of 3*/
        free(head);

        return 0;
}

void add_item(struct x **ptr, double data)
{
        struct x *item = malloc(sizeof *item);

        item->value = data;
        item->next = *ptr;
        *ptr = item;
}


void multiply (struct x *head, struct x *end)
{
        double result;

        if (head == end)
                return;

        if (head->next != end) {
                result = (head->next)->value * head->value;
                head->value = result;
                del(head);
                multiply(head, end);
        }
}

void add (struct x *head, struct x *end)
{


        if (head == end)
                return;

        if (head->next != end) {
                head->value = (head->next)->value + head->value;
                del(head);
                add(head, end);
        }
}

void del (struct x *before_del)
{
        struct x *temp;
        temp = before_del->next;
        before_del->next = temp->next;
        free(temp);
}