c - 括号平衡检查器总是给出不正确的输出

我正在尝试创建一个函数,该函数使用 linked list 检查表达式是否平衡(左括号数 = 右括号数)或不平衡。但是我的函数总是给出“不平衡”作为输出。

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

struct LL
{
    char data;
    struct LL *next;
};

int isEmpty(struct LL *top)
{
    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isFull(struct LL *top)
{
    struct LL *n = malloc(sizeof(struct LL *));
    if (n == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

struct LL *push(struct LL *top, char x)
{
    if (isFull(top))
    { 
        printf("Stack Overflow\n");
    }
    else
    {
        struct LL *n = malloc(sizeof(struct LL));
        n->data = x;
        n->next = top;
        top = n;
    }
    return top;
 }

 struct LL *pop(struct LL *top)
 {
    if (isEmpty(top))
    {
        printf("Stack Underflow\n");
    }
    else
    {
        struct LL *n = malloc(sizeof(struct LL));
        n = top;
        top = top->next;
        free(n);
    }
    return top;
 }

 int BracketBalancing (char *exp)
 {
    struct LL *top = malloc(sizeof(struct LL));
    top->next = NULL;
    for (int i = 0; exp[i] != '\0'; i++)
    {
        if (exp[i] == '(')
        {
            push(top, exp[i]);
        }
        else if (exp[i] == ')')
        {
            if (isEmpty(top))
            {
                return 0;
            }
            pop(top);
        }
    }
    if (isEmpty(top))
    {
        return 1;
    }
    else
    {
        return 0;
    }
  }

主要代码:

int main(int argc, char const *argv[])
{
    int n;
    char *expression = (char *)malloc(sizeof(char));
    printf("Enter the length of the expression for Bracket Balancing\n");
    scanf("%d", &n);
    printf("Enter the expression for Bracket Balancing\n");
    for (int i = 0; i < n; i++)
    {
        scanf("%c ", &expression[i]);
    }
    getchar();
    if (BracketBalancing(expression))
    {
        printf("The expression is balanced\n");
    }
    else if (!BracketBalancing(expression))
    {
        printf("This expression is unbalanced\n");
    }
    return 0;
}

例如:

输入:

Enter the length of the expression for Bracket Balancing 
4
Enter the expression for Bracket Balancing
1+()

输出:

This expression is unbalanced

在上面的例子中,没有。开括号 = 没有。右括号(这是一个平衡的表达式),但生成的输出仍然是“这个表达式是不平衡的”。请更正我的代码。

回答1

这是您初始化列表的方式:

struct LL *top = malloc(sizeof(struct LL));
top->next = NULL;

这是 isEmpty()

int isEmpty(struct LL *top)
{
    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

但是:top 以 value != NULL 开头,所以 isEmtpy() 不会返回 1,尽管我们的列表一开始应该是空的。

当您传递 NULL 时,您的 push() 实现应该可以正常工作,因此您可以只初始化 struct LL *top = NULL; 而不是立即创建第一个元素。

您的代码中还有其他错误,例如:

  • pop() 你做

    struct LL *n = malloc(sizeof(struct LL));
      n = top;

这样malloc()的结果直接在下一行overwritten()

  • isFull() 中,当您调用 malloc() 并且从不使用或 free() 返回的缓冲区时会产生内存泄漏。该函数无论如何都没有意义,只需检查 malloc()s 的结果,您确实想在其中使用返回的缓冲区。

** 编辑 **

我以前没见过的是,你也从不使用 push()pop() 的返回 value,所以由这些函数确定的新顶部丢失了。将 push(top, ...); 替换为 top = push(top,...); 并将 pop(top); 替换为 top = pop(top);

相似文章

python - Pandas merge 具有多列的数据框

我正在尝试merge2个数据帧,但在弄清楚如何做时遇到了问题,因为它不是直截了当的。一个数据框有超过25000场比赛的匹配结果,看起来像这样。第二个具有团队绩效指标,但仅适用于大约1500场比赛。由于...

javascript - 伊朗平均成绩 Regex

我需要一个regex来处理伊朗平均成绩,regex应该涵盖所有这些规则数字范围应在0到20之间。数字可以是十进制,但20除外。整数部分和小数部分应包含一或两个数字。如果您使用“。”你应该至少有一个十进...