题目描述

请写一个程序，判断给定表达式中的括号是否匹配，表达式中的合法括号为”(“, “)”, “[", "]“, “{“, ”}”,这三个括号可以按照任意的次序嵌套使用。

输入

有多个表达式，输入数据的第一行是表达式的数目，每个表达式占一行。

输出

对每个表达式，若其中的括号是匹配的，则输出”yes”，否则输出”no”。

样例输入

4
[(d+f)*{}]
[(2+3))
()}
[4(6]7)9

样例输出

yes
no
no
no

思路：用stack以及map，通过map将”(“, “)”, “[", "]“, “{“, ”}”他们中的任何两个绑在一起。输入一个字符串后，如果字符串的元素是括号，则将其入栈，如果该括号正和栈顶元素是一对，则将栈顶元素出栈。最后，如果栈为空，则表示是合法的，若不为空，则不合法。

#include <iostream>
#include <cstdio>
#include <map>
#include <stack>
#include <string>
using namespace std;

int main()
{
	map<char,char> mp;
	stack<char> s;
	mp['(']=')';
	mp['{']='}';
	mp['[']=']';
	mp[')']='(';
	mp['}']='{';
	mp[']']='[';
	int n;
	string str;
	while(scanf("%d\n",&n)!=EOF){
		for(int i=0;i<n;i++){
			getline(cin,str);
			for(int j=0;j<str.length();j++){
				if(!s.empty()&&mp[s.top()]==str[j]){
					s.pop();
					continue;
				}
				if(str[j]=='{'||str[j]=='['||str[j]=='('||str[j]=='}'||str[j]==']'||str[j]==')')
					s.push(str[j]);
			}
			if(s.empty()) printf("yes\n");
			else printf("no\n");
			while(!s.empty()) s.pop();
		}
	}
	return 0;
}