c语言括号匹配问题(栈) 我写的程序感觉有点错 找不到原因

2025-04-01 02:13:41
推荐回答(1个)
回答1:

大概有这3个问题:

  1.  资源没有清理

  2.  部分逻辑错误

  3.  栈操作错误

带注释修改如下:

#include
#include
#include

struct Node
{
    char fuhao;
    struct Node *next;
};
struct S
{
    struct Node *top;
    struct Node *bottom;
};

void start(struct S *s);
void clean(struct S *s);
void end(struct S **s);

char yulan(struct S *s);
void ruzhan(struct S *s, char a);
char chuzhan(struct S *s);
int panduan(struct S *s);

int match(char a, char b);

int main()
{
    int n, a, i;
    char arr[256], in, out;
    scanf("%d", &n);
    fflush(stdin);    // 清空输入缓存
    struct S *s = (struct S *)malloc(sizeof(struct S));
    start(s);    // 创建第一个node(bottom),可以放在while外面
    while (n>0)
    {
        int onlyr = 0;  // 如果表达式消除后只剩右*符号,则设为 1
        gets(arr);
        a = strlen(arr);
        for (i = 0; i        {
            char fh = arr[i];
            if (fh == '(' || fh == '[' || fh == '{')
            {
                in = fh;
                ruzhan(s, in);
            }
            else if (fh == ')' || fh == ']' || fh == '}')
            {
                out = yulan(s);
                if (out == '\0')
                    onlyr = 1;
                if (!match(out, fh))
                    break;
                else
                    chuzhan(s);
            }
        }
        if (panduan(s) && !onlyr)
            printf("YES\n");
        else
            printf("NO\n");

        clean(s);
        n--;
    }
    end(&s);
    return 0;
}

// 预览top,s->top在end之前都会有效
char yulan(struct S *s)
{
    if (s->top)
        return s->top->fuhao;
    return '\0';
}

int match(char a, char b)
{
    return  ((a == '(' && b == ')') ||
             (a == '[' && b == ']') ||
             (a == '{' && b == '}'));
}

// 这个栈在end之前始终有个node,bottom始终指向这个node
void start(struct S *s)
{
    struct Node *p = (struct Node *)malloc(sizeof(struct Node));
    p->fuhao = '\0';
    p->next = 0;

    s->top = p;
    s->bottom = p;    
}

// 只保留bottom,清空其他node
void clean(struct S *s)
{
    struct Node *p = s->top;
    while (p && p != s->bottom) {
        struct Node *q = p->next;
        free(p);
        p = q;
    }
    //除了bottom其他都已经清除了,把top指针指向bottom
    s->top = s->bottom;
}

// 全部清除,包括 s栈 本身
void end(struct S **s)
{
    clean(*s);
    free((*s)->bottom);
    free(*s);
    *s = 0;
}

void ruzhan(struct S *s, char a)
{
    struct Node *p;
    p = (struct Node *)malloc(sizeof(struct Node));
    p->next = s->top;
    p->fuhao = a;

    s->top = p;
}

char chuzhan(struct S *s)
{
    // 空栈直接返回'\0'
    if (s->top == s->bottom) {
        return '\0';
    }
    char c;
    struct Node *p;
    p = s->top;
    c = s->top->fuhao;

    s->top = s->top->next;
    
    free(p);
    return c;
}

int panduan(struct S *s)
{
    return (s->top == s->bottom);
}