先放一个题目:

小明今年上大学,在大学里发现有很多同学都女朋友,两人整天都在一起腻歪,小明看到后感 觉很孤单,现在,给你一行括号序列,你来判断一下其中的括号是否配对。

第一行输入一个数N(0<n<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组 输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保 证S中只含有”[”, ”]”, ”(”, ”)” 四种字符 ,输入以“EOF”结束。

输出

每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则 输出No。

输入样例

3

[(])

(])

([[]()])

输出样例

No

No

Yes

 

这个题目算是ACM里面非常基础的题目,主要考点是栈和队列。

在我年少无知的时候,我第一次见到这个题,用的还是非常原始的方法:

1.

首先这是一个字符串,那我们就用字符的方式来解决他。

首先,要记住一句名言:

代码是人的思想的体现

                           ----沃兹基硕德

如果把这一串字符串放在纸上,那么我们用的方法肯定是找到一对擦掉一对,然后直到找不到可以擦去的为止。

如果有剩余的没被擦去的,那结果就是no,否则就是yes。

然后就可以来水题了。

//这种方法只适用于数据比较小的时候 

#include<stdio.h>
#include<string.h>
int main()
{
	char str[10010];
	int n;
	scanf("%d",&n);
	while(n--){
		scanf("%s",str);
		int len=strlen(str);
		char vis=' ';
		int pos,i,j;
		while(1){//只要能找到配对的括号,就一直找下去(判断条件为是否遍历一遍所有的字符) 
			for(i=0;i<len;i++){
				//用橡皮擦把凑好的一对擦去
				if(vis=='[' && str[i]==']'){ 
					str[pos]=' ';
					str[i]=' '; 
					break;
				}
				if(vis=='(' && str[i]==')'){ 
					str[pos]=' ';
					str[i]=' ';
					break;
				}
				if(str[i]!=' ')
					pos=i,vis=str[i];
			}
			if(i==len)
				break; 
		}
		for(i=0;i<len;i++){
			if(str[i]!=' ') break;
		}
		if(i==len)	printf("Yes\n");
		else	printf("No\n");
	}
	return 0;
}

2.

接下来就是比较高级的做法了(至少比上一个高级)栈:

栈的特性即为先进后出,所以我们每次储存一个字符,然后判断是否有和它相匹配的字符,有的话就出栈,没有的话继续入栈,直到最后一个元素。

代码如下:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
int main()
{
    char str[10010];
    int len,t,i,j,n;
    scanf("%d",&t);
    while(t--){
        stack<char>sta;
        scanf("%s",str);
        len=strlen(str);
        sta.push(str[0]);
        for(i=1;i<len;i++){
            if(sta.top()=='(' && str[i]==')'){
                sta.pop();
            }
            else if(sta.top()=='[' && str[i]==']'){
                sta.pop();
            }
            else sta.push(str[i]);
        }
        if(sta.empty()){
            printf("Yes\n");
        }
        else printf("No\n");
    }
    return 0;
}