C使用堆栈作为链表的平衡括号

Question

我正试图在C中使用Stack作为链表来编写平衡括号。我面临的问题是，当测试用例值为3时，前两个测试用例运行良好，但最后一个测试用例总是显示NO作为输出。例如：如果输入为：

3
{[()]}
{[(])}
{{[[(())]]}}

预期输出为：

YES
NO 
YES

实际输出为：

YES
NO 
NO

#include <stdio.h>
#include <stdlib.h>
struct Node
{
char data;
struct Node *next;
}*top = NULL;
void push(char x)
{
struct Node *t;
t = (struct Node *)malloc(sizeof(struct Node));
if(t == NULL)
printf("Stack is Overflown");
else
{
t->data = x;
t->next = top;
top=t;
}
}
char pop()
{
char x = -1;
struct Node *p;
if(top == NULL)
printf("Stack is Underflown");
else
{
p=top;
top=top->next;
x=p->data;
free(p);
}
return x;
}
int isEmpty()
{
return top?0:1;
}
char stackTop()
{
if(!isEmpty())
return top->data;
return '0';
}
int isBalanced(char *exp)
{
int i;
for(i=0;exp[i]!='';i++)
{
if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
push(exp[i]);
else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
{
if(isEmpty())
return 0;
if(stackTop() == '(' && exp[i] == ')')
pop();
else if(stackTop() == '{' && exp[i] == '}')
pop();
else if(stackTop() == '[' && exp[i] == ']')
pop();
else
return 0;
}
}
if(isEmpty())
return 1;
else
return 0;
}

int main()
{
char *exp;
int t;
scanf("%d",&t);
while(t--)
{
exp = (char*)malloc(10000*sizeof(char));
scanf("%s",exp);
if(isBalanced(exp))
printf("YESn");
else 
printf("NOn");
free(exp);
}
return 0;
}

Answer 1

您在处理完每种情况后都忘记了重置堆栈。

while(t--)
{
exp = (char*)malloc(10000*sizeof(char));
scanf("%s",exp);
if(isBalanced(exp))
printf("YESn");
else 
printf("NOn");
free(exp);
while (!isEmpty()) pop(); /* add this */
}

Answer 2

#include<iostream>
using namespace std;
struct Node{
char data;
struct  Node *next;
}*top = NULL;
void push(char x){
struct Node *t;
t = new Node;
if(t == NULL){
cout<<"Stack is full"<<endl;
}
else{
t->data = x;
t->next = top;
top = t;
}

}
char pop(){
char x = -1;
struct Node *p;
if(top == NULL){
cout<<"stack is empty"<<endl;
}
else{
p = top;
top = top->next;
x = p->data;
delete p;
}
return x;
}
char stackTop(){
if(top){
return top->data;
}
return '0';
}
int isBalanced(char exp[]){
int i;
for(i = 0 ; exp[i] != '';i++){
if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{'){
push(exp[i]);
}
else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}'){
if(top == NULL){
return 0;
}if( stackTop() == '(' && exp[i] == ')'){
pop();
}else if(stackTop() == '{' && exp[i] == '}'){
pop();
}else if(stackTop() == '[' && exp[i] == ']'){
pop();
}else{
return 0;
}
}
}
return top == NULL? 1 : 0;
}
int main(){
// exp
char  exp[] = "{([a+b]*(b-c])}";
if(isBalanced(exp)){
cout<<"Balanced Parenthesis"<<endl;
}else{
cout<<"Not Balanced"<<endl;
}

return 0;
}