先放一个题目：

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

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

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出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;
}

括号问题

1.

2.