大概有这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);
}