https://ybt.ssoier.cn/problem_show.php?pid=1355

评测记录 https://ybt.ssoier.cn/status.php?showname=zfy201112282658&showpid=1355

#include <bits/stdc++.h>
using namespace std;
//#define int long long
stack<char> stk;
int x[300];
bool isup(char c)
{
	return c=='<'||c=='('||c=='['||c=='{';
}
bool isdown(char c)
{
	return c=='>'||c==')'||c==']'||c=='}';
}
bool ABC(char a,char b)
{
	return x[a]>=x[b];
}
bool CBA(char a,char b)
{
	return x[a]<=x[b];
}
void AAA()
{
	string str;
	cin>>str;
	for(int i=0;str[i];i++)
	{
		if(str[i]=='<'||str[i]=='('||str[i]=='['||str[i]=='{') stk.push(str[i]);
		else
		{
			if(str[i]=='}')
			{
				if(!stk.empty()&&stk.top()=='{') stk.pop();
				else
				{
					cout<<"NO";
					return;
				}
			}
			if(str[i]==']')
			{
				if(!stk.empty()&&stk.top()=='[') stk.pop();
				else
				{
					cout<<"NO";
					return;
				}
			}
			if(str[i]==')')
			{
				if(!stk.empty()&&stk.top()=='(') stk.pop();
				else
				{
					cout<<"NO";
					return;
				}
			}
			if(str[i]=='>')
			{
				if(!stk.empty()&&stk.top()=='<') stk.pop();
				else
				{
					cout<<"NO";
					return;
				}
			}
		}
	}
	if(!stk.empty()) cout<<"NO";
	else
	{
		for(int i=1;str[i];i++)
		{
			int b = str[i];
			int a = str[i-1];
			if(isup(a)&&isup(b))
			{
				if(!ABC(a,b))
				{
					cout<<"NO";
					return;
				}
			}
			else if(isdown(a)&&isdown(b))
			{
				if(!CBA(a,b))
				{
					cout<<"NO";
					return;
				}
			}
		}
		cout<<"YES";
	}
}
signed main()
{
//	freopen("strs.in","r",stdin);
//	freopen("strs.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	x['<'] = x['>'] = 1;
	x['('] = x[')'] = 2;
	x['['] = x[']'] = 3;
	x['{'] = x['}'] = 4;
	int q;
	cin>>q;
	while(q--)
	{
		AAA();
		cout<<"\n";
	}
	return 0;
}