字符串匹配问题——带有优先级的括号匹配问题
题⽬描述
字符串中只含有括号 (),[],<>,{}，判断输⼊的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输⼊: [()]输出:YES，⽽输⼊([])，([)]都应该输出 NO。
输⼊
第⼀⾏为⼀个整数 n，表⽰以下有多少个由括好组成的字符串。接下来的 n ⾏，每⾏都是⼀个由括号组成的长度不超过 255 的字符串。
输出
有 n ⾏（n≤20），每⾏都是 YES 或 NO。
样例输⼊
5
{}{}<><>()()[][]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{{}}{{}}<<>><<>>(())(())[[]][[]]
{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
样例输出
YES
YES
YES
YES
NO
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define wuyt main
typedef long long ll;
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
正则匹配括号里的内容#define read read()
const ll inf = 1e15;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
#define start int wuyt()
#define end return 0
/
**int dfs(int n,int k)
{
if((n==0)||(k==0)||(n<k))
return 0;
if(k==1||n==k)
return 1;///only1
return dfs(n-k,k)+dfs(n-1,k-1);
}**/
char ss[maxn];
int num[maxn];
start{
ll n=read;
while(n--)
{
cin>>ss;
for(int i=0;i<strlen(ss);i++)
{
if(ss[i]=='<') num[i]=1;
else if(ss[i]=='>') num[i]=2;
else if(ss[i]=='(') num[i]=3;
else if(ss[i]==')') num[i]=4;
else if(ss[i]=='[') num[i]=5;
else if(ss[i]==']') num[i]=6;
else if(ss[i]=='{') num[i]=7;
else if(ss[i]=='}') num[i]=8;
}
stack<int> s;
bool flag=true;
for(int i=0;i<strlen(ss);i++)
{
pty()) s.push(num[i]);
else{
if(num[i]%2==1){
if(num[i]<=s.top()) s.push(num[i]);
else {
flag=false;
break;
}
}
else if(num[i]-1==s.top())
s.pop();
}
}
pty()&&flag) printf("YES\n");
else printf("NO\n");
}
end;
}
前⾯哪⼀种是错误的⽅法，没有看到需要考虑类似优先级这样的问题

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。