C++ 代码
使用栈模拟,规则如下:
1. 碰到左括号,入栈时比较优先级关系是否合理
2. 碰到右括号,检查栈顶元素是否匹配
3. 在前两条规则满足时,最后判断栈是否为空,如:())的情况
#include <iostream>
#include <unordered_map>
#include <stack>
using namespace std;
int main()
{
int t;
unordered_map<char, int> pr{{'(', 1}, {'(', 1},
{'[', 2}, {']', 2},
{'{', 3}, {'}', 3}};
cin >> t;
while(t --)
{
string str;
stack<char> s;
cin >> str;
bool flag = true;
for(int i = 0; i < str.size(); i ++)
{
char c = str[i];
if(c == '(' || c =='[' || c=='{' || c == '<')
{
if(!s.empty() && pr[s.top()] < pr[c]) // ([])
{
flag = false;
break;
}
s.push(c);
}
else
{
if(c == '>')
{
if(s.empty() || s.top() != '<')
{
flag = false;
break;
}
}
else if(c == ')')
{
if(s.empty() || s.top() != '(')
{
flag = false;
break;
}
}
else if(c == ']')
{
if(s.empty() || s.top() != '[')
{
flag = false;
break;
}
}
else if(c == '}')
{
if(s.empty() || s.top() != '{')
{
flag = false;
break;
}
}
s.pop();
}
}
if(flag == false) cout << "NO" << endl;
else
{
if(s.empty()) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
return 0;
}