swust oj 0116 括号匹配
14级卓越班选拔D 15级卓越班选拔D 16级卓越班选拔D
题意描述： 在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。包括有大括号{}，中括号[]，小括号()，尖括号<>等。 对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号。例如，{[()]}，{()},{ {}}为一个合法的表达式，而([{}])，{([])},[{<>}]都是非法的。
Description
文件的第一行为一个整数n（1≤n≤100），接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。
Input
在输出文件中有N行，其中第I行对应第I个表达式的合法性，合法输出YES，非法输出NO。
Output
| 1 2 3 4 5 6 | 5 {[(<>)]} [()] <>()[]{} [{}] {()} |
Sample Input
| 1 2 3 4 5 6 | YES YES YES NO YES |
鬼知道为什么scanf会超时，cin就不会，整整搞了我两天，还以为自己算法有问题==
//by swust_t_p
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<string.h>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
int main()
{
int n;
cin >> n;
while (n--)
{
char a[100];
cin >> a;
stack<char>b;
int f = 1;
for (int i = 0; a[i] != 0; i++)
{
// （40 <60 [91 {123
if (a[i] == '[' || a[i] == '(' || a[i] == '{' || a[i] == '<')
{
if (b.empty())
{
b.push(a[i]);
continue;
}
else if (a[i] > b.top() && a[i] != '<')
{
f = 0;
break;
}
else if (a[i] == '(' && b.top() == '<')
{
f = 0; break;
}
/*else if (a[i] == '<')
{
b.push(a[i]);
}*/
else
{
b.push(a[i]);
}
}
else if (a[i] == ']' || a[i] == ')' || a[i] == '}' || a[i] == '>')
{
if (b.empty())
{
f = 0;
break;
}
if (!b.empty() && a[i] == b.top() + 1 || a[i] == b.top() + 2)
{
b.pop();
}
else
{
f = 0;
break;
}
}
}
if (!b.empty())
{
f = 0;
}
if (f)
{
cout << "YES" << '\n';
}
else
{
cout << "NO" << '\n';
}
}
return 0;
}//by swust_t_p
Momenta公司福利 293人发布