1476: 括号括号————（STL，栈的模拟）

清疚 2022-05-17 21:13 98阅读 0赞

1476: 括号括号  
时间限制: 3 Sec 内存限制: 128 MB

提交: 339 解决: 66 统计  
**题目描述**  
小明今年上大学，在大学里发现有很多同学都女朋友，两人整天都在一起腻歪，小明看到后感觉很孤单，现在，给你一行括号序列，你来判断一下其中的括号是否配对。  
**输入**  
多组输入，每一组第一行输入一个数 T （ 0 < < N ≤ ≤ 100 ） T（0<<N≤≤100） T（0<<N≤≤100）,表示有T组测试数据。后面的T行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"\[", “\]”, “(”, “)” 四种字符

**输出**  
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No。  
**样例输入**  
3  
\[(\])  
(\])  
(\[\])  
**样例输出**  
No  
No  
Yes  
**来源**  
刘帅坤

--------------------

这道题在输入输出的时候有个坑点，就是输入n的时候也需要

while(~scanf("%d",&n))
    {
    	while(n--)
    	{
    		//这里写内容
    	}
    }

然后就用一个栈来模拟就行了，不能匹配的括号直接推到栈里，感觉这道题和消消乐有点儿像，能够匹配的，就可以直接消除，不能够匹配的还存在里边，

这道题并不是统计左括号和有括号的数目然后匹配的

只有左括号在左边，有括号在右边，如果左右括号中间有东西的话，中间的括号也是能够匹配才行  
匹配： \[ ( ) \] \[(\\ )\] \[()\]， \[ \] \[ \] \[ \] \[ \] \\quad \[\\ \]\[\\ \]\[\\ \]\[\\ \] \[\]\[\]\[\]\[\], \[ \[ \] ( ) \] \\quad \[\\ \[\\ \]\\ (\\ )\\ \] \[\[\]()\], ( \[ \[ \] ( ) \] ) \\quad (\\ \[\\ \[\\ \](\\ )\\ \]\\ ) (\[\[\]()\])  
不匹配： \] \[ \] \[ \] \[ , \[ ( \] ) \]\[\\ \]\[\\ \]\[\\ ,\\quad \[\\ (\\ \]\\ ) \]\[\]\[\]\[,\[(\])  
规则就是这样子，然后找  
我就是把这个字符串直接遍历一遍，一个一个的判断是否可以推到栈里  
先把s\[0\]推到栈里  
对于字符串里的每一个字符  
如果能够推到栈里，那么这个字符就是栈顶  
在判断在字符串里的下一个字符看看是否与栈顶元素匹配  
如果匹配，那么就把栈顶元素取出，在判断字符串里的下一个字符

如果括号全部匹配，那么栈的大小为0，输出Yes，否则输出No

--------------------

code：

#include<bits/stdc++.h> 
    using namespace std;
    const int MAXN=1e4+9;
    int main()
    {
    	char s[MAXN];
    	int n;
    	while(~scanf("%d",&n))
    	{
    		while(n--)
    		{
    			scanf("%s",s);
    			int len=strlen(s);
    			stack<char> sta;
    			sta.push(s[0]);
    			for(int i=1;i<len;i++)
    			{
    				if(sta.size()&&s[i]==']'&&sta.top()=='[')
    				{
    					sta.pop();
    					continue;
    				}
    				if(sta.size()&&s[i]==')'&&sta.top()=='(')
    				{
    					sta.pop();
    					continue;
    				}
    				sta.push(s[i]);
    			 } 
    			if(sta.size())	printf("No\n");
    			else			printf("Yes\n");
    		}
    	 } 
    	return 0;
    }