合法的括号串

野性酷女 2021-12-11 23:59 252阅读 0赞

## 题目描述 ##

一个合法的括号串，是指只包含括号的串，如果满足如下条件：

（1）<> () \[\] \{\} 这四对括号是合法的；

（2）如果r是合法括号串，则 ® \[r\] \{r\}也是；

（3）如果r，s是合法括号串，则rs也是；

所以<<>> , \[<>\{\}(())\],\[(\{<>\})\]是合法的括号串，而)(,\[( \])就不是。

【输入形式】

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。

后面有t行，每行一个只包含8种括号符号的括号串。

40%的括号串的长度L 2 ≤ L≤ 20；

30%的括号串的长度L 2 ≤ L≤ 200；

20%的括号串的长度L 2 ≤ L≤ 2000；

10%的括号串的长度L 2 ≤ L≤ 20000；

【输出形式】

对于每组测试数据，如果括号串是合法的，输出“Yes”（输出没有引号）占一行，否则，输出“No”（输出没有引号）占一行。

【样例输入】

6  
<<>>  
)(  
\[<>\{\}(())\]  
\[(\{<>\})\]  
\[(\])  
<(\[\{  
【样例输出】

Yes  
No  
Yes  
Yes  
No  
No

## AC代码 ##

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    int main()
    {
    	int n;
    	cin>>n;
    	while(n--){
    		stack<char> s;
    		string str;
    		cin>>str;
    		int len = str.length();
    		int i;
    		for(i=0; i<len; ++i){
    			if(str[i]=='<'||str[i]=='{'||str[i]=='('||str[i]=='[') s.push(str[i]);
    			else if(str[i]=='>'){
    				if(!s.empty()&&s.top()=='<') s.pop();
    				else{
    					cout<<"No"<<endl;
    					break;
    				} 
    			}
    			else if(str[i]==')'){
    				if(!s.empty()&&s.top()=='(') s.pop();
    				else{
    					cout<<"No"<<endl;
    					break;
    				} 
    			}
    			else if(str[i]==']'){
    				if(!s.empty()&&s.top()=='[') s.pop();
    				else{
    					cout<<"No"<<endl;
    					break;
    				} 
    			}
    			else if(str[i]=='}'){
    				if(!s.empty()&&s.top()=='{') s.pop();
    				else{
    					cout<<"No"<<endl;
    					break;
    				} 
    			}
    		if(i==len-1&&s.empty()) cout<<"Yes"<<endl;
    		if(i==len-1&&!s.empty()) cout<<"No"<<endl;
    		}
    	}
    	return 0;
    }