2009年西电计算机研究生复试上机题（3）

题目描述

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

 
输入

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

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

 
样例输入

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

 
样例输出

yes
no
no
no

 
提示 [+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

 
来源

2009年西电计算机研究生复试上机题

 

/********************************* 
 *    日期：2013-3-11
 *    作者：SJF0115 
 *    题号: 天勤OJ 题目1219: Problem E
 *    来源：http://acmclub.com/problem.php?id=1219
 *    结果：AC 
 *    来源：2009年西电计算机研究生复试上机题 
 *    总结： 
**********************************/ 
#include<iostream>
#include<string.h>
#include<stack>
#include<stdio.h>
using namespace std;

char array[1001];

int main(){
int N,i,tag;
while(scanf("%d",&N) != EOF){
//N组测试数据
while(N--){
stack<char> Stack;
scanf("%s",array);
for(i = 0;i < strlen(array);i++){
//只考虑括号，其他字符不用考虑
if(array[i] == '{' || array[i] == '}' || array[i] == '[' || array[i] == ']' || array[i] == '(' || array[i] == ')'){
//如果栈为空或者字符为{,[,(则入栈
if(Stack.empty() || array[i] == '{' || array[i] == '[' || array[i] == '('){
Stack.push(array[i]);
}
else{
//判断是否匹配
if((array[i] == '}' &&  Stack.top() == '{') || (array[i] == ']' &&  Stack.top() == '[') || (array[i] == ')' &&  Stack.top() == '(')){
Stack.pop();
}
}
}//if
}
if(!Stack.empty()){
printf("no\n");
}
else{
printf("yes\n");
}
}//while
}//while
return 0;
}