AcWing 3703. 括号的匹配
原题链接
简单
作者:
Jackyc
,
2021-06-22 15:35:34
,
所有人可见
,
阅读 501
#include<iostream>
#include<unordered_map>
#include<stack>
#include<string>
using namespace std;
string str;
unordered_map<char, int> pr{{'{',3}, {'[', 2}, {'(', 1}, {'<', 0}};
stack<char> S;
unordered_map<char, char> mp {{'{', '}'}, {'[', ']'}, {'(', ')'}, {'<', '>'}};
bool flag;
//入栈是否满足要求
void check1(char ch){
if(!S.size() || pr[ch] <= pr[S.top()]) S.push(ch);
else flag = false;
}
//弹栈是否满足要求
void check2(char ch){
if(!S.size()) flag = false;
else{
char t = S.top();
if(mp[t] == ch) S.pop();
else flag = false;
}
}
int main(){
int T;
cin >> T;
while(T --){
cin >> str;
//每次样例清空栈
while(S.size()) S.pop();
flag = true;
for(int i = 0; i < str.size(); i ++){
if(str[i] == '{' || str[i] == '[' || str[i] == '(' || str[i] == '<') check1(str[i]);
else check2(str[i]);
if(!flag) break;
}
//最后还需判断栈是否为空,即全部配对完毕
if(S.size()) flag = false;
if(flag) puts("YES");
else puts("NO");
}
return 0;
}