nyoj-括号匹配问题
括号配对问题
时间限制：3000 ms | 内存限制：65535 KB
难度：3
描述现在，有一行括号序列，请你检查这行括号是否配对。
输入第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符输出每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No样例输入
3
[(])
(])
([[]()])样例输出
No
No
Yes来源网络上传者naonao问题分析----这种问题一般是从里到外进行配对比如第三个（【【】（）】）先进行里面的判断【】（）两个配对，所以剪掉，形成新的链表（【】）再判断【】，显然配对所以剩下()，依次这样最后得到head（指针）为NULL，如果最后为NULL，则作为完全匹配，否则作为不完全配对......实现代码： （c语言版）由于c++的sTL写，太简单了，就不写了；
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct NODE
{
char a;
struct NODE *next ;
}Node;
int main( void )
{
int n,t,flag;
Node *head,*p1,*p2;
scanf("%d",&t);
getchar();
while(t--)
{
head=NULL;
flag=n=0;
p1=p2=(Node*)malloc(sizeof(Node));
while(p1->a=getchar(),p1->a!='\n')
{
if(++n==1)head=p1;
else p2->next=p1;
p2=p1;
p1=(Node *)malloc(sizeof(Node));
}
p2->next=NULL;
/* p1=head;
while(p1!=NULL)
{
putchar(p1->a);
p1=p1->next;
}
puts("");*/
while(1)
{
p2=p1=head;
n=flag=0;
while(p1!=NULL&&p1->next!=NULL)
{
if(n++!=0)p1=p1->next;
if(p1->next==NULL)break;
if((p1->a=='('&&p1->next->a==')')||(p1->a=='['&&p1->next->a==']'))
{
flag=1;
if(p1==head)
{
p1=p1->next;
head=p1->next;
}
else
{
p1=p1->next;
p2->next=p1->next;
}
}
else
p2=p1;
}
/* p2=p1=head;
while(p1!=NULL)
{
putchar(p1->a);
p1=p1->next;
}
if(p2!=NULL) puts("");*/
if(!flag)break;
}
puts(head==NULL?"Yes":"No");
free(head);
// free(p1);
// free(p2);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-07-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录