练习场 002 括号配对问题
括号配对问题
时间限制:3000 ms | 内存限制:65535 KB
难度:3
描述:
现在,有一行括号序列,请你检查这行括号是否配对。
输入第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[", “]”, “(”, “)” 四种字符输出每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No
样例输入:
3
[(])
(])
([[]()])
样例输出:
No
No
Yes
来源:网络 ;上传者 naonao
题目网址:(http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=2)
题意:
本题就是用来判断括号配对是否正确。
思路:
本题输入字符串,然后对字符串进行遍历,遇到左括号时存到一个新的数组中,遇到右括号时对数组中的最后一个进行匹配,匹配不成功结束并输出No,匹配成功把数组中的最后一个元素删除,在遍历的过程中还要判断左括号和右括号的数量是不是相同。
代码:
#include<stdio.h>
#include<string.h>
char a[10005],b[10005],c[10005];
int main()
{
int n,i,j,d,q,w;
scanf("%d",&n); //输入n表示有n组数据
for(i=0;i<n;i++)
{
q=0;
w=0;
scanf("%s",a);
d=strlen(a); //字符串的长度
if(d>1&&d%2==0) //判断字符串的长度是否为偶数
{
for(j=0;j<d;j++)
{
if(a[j]=='['||a[j]=='(') //左括号存到数组b中
{
b[q]=a[j];
q++;
}
else if(a[j]==']') //右括号判断与前一个走括号是否匹配
{
w++;
if(b[q-1]!='[') //匹配不成功结束
{
break;
}
else //成功w--,q--
{
w--;
q--;
}
}
else
{
w++;
if(b[q-1]!='(')
{
break;
}
else
{
w--;
q--;
}
}
}
if(q==0&&w==0) //判断是否匹配完全并输出Yes或No
printf("Yes\n");
else
printf("No\n");
}
else
printf("No\n");
}
}
运行结果:
总结:
本题用栈写的话会很简单的,上面的第一种是用数组写的,思想也是栈的思想,后进先出,用来判断右括号是否和它前面的左括号匹配。