5. 合法的括号串

【问题描述】

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

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

（2）如果r是合法括号串，则<r> (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；

#include<iostream>
#include<stack>
using namespace std;
char s(char);//返回与之搭配的字符串
int main() {
	int t;
	cin>>t;
	for(int i=0; i<t; i++) {
		string str;
		cin>>str;
		stack<char>mystack;//用栈 
		for(int j=0; j<str.size(); j++) {//for循环将该字符串进行遍历 
			if(mystack.empty()) {
				mystack.push(str[j]);//栈为空就将当前字符压进去
				continue;
			}
			if(s(mystack.top())==str[j])mystack.pop();//如果栈的顶部元素与该字符匹配就出栈
			else mystack.push(str[j]);//不为空不匹配时也压进去 
		}
		if(mystack.empty())cout<<"Yes"<<endl;//最后如果栈为空，说明字符串合法 
		else cout<<"No"<<endl;
	}
	return 0;
}
char s(char a) {
	char key=0;
	if(a=='{')key='}';
	if(a=='<')key='>';
	if(a=='[')key=']';
	if(a=='(')key=')';
	return key;
}