关于这题目的正确匹配

P1241 括号序列

方123456 @ 2020-10-25 14:08:50

RT,同时求助我的代码为什么 63pts?

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF=105;
char s[INF];
int q1[INF],q2[INF],r1,r2;
bool vis1[INF],vis2[INF],vis11[INF],vis22[INF];
signed main()
{
        scanf("%s",s); int len=strlen(s);
        for (int i=0; i<len; i++) {
                if (s[i]=='(') {q1[++r1]=i; vis1[i]=true;}
                if (s[i]==')') {
                        if (r1>0) {if (r2>0) {while (q2[r2]>q1[r1]) r2--; } vis1[q1[r1]]=false; r1--; }
                        else vis11[i]=true;
                }
                if (s[i]=='[') {q2[++r2]=i; vis2[i]=true;}
                if (s[i]==']') {
                        if (r2>0) {if (r1>0) {while (q1[r1]>q2[r2]) r1--; } vis2[q2[r2]]=false; r2--; }
                        else vis22[i]=true;
                }
                // for (int i=1; i<=r2; i++) cout<<q2[i]<<" ";
                // cout<<endl;
        }
        for (int i=0; i<len; i++) {
                if (vis11[i]) cout<<'(';
                if (vis22[i]) cout<<'[';
                cout<<s[i];
                if (vis1[i]) cout<<')';
                if (vis2[i]) cout<<']';
        }
        return 0;
}

还有就是 [((])) 这种括号到底怎么匹配呀?


by imfkwk @ 2021-01-25 00:40:53

我的运行结果是[]()()[]()()。这很明显是错的。

如果按照规则来看,你有很多种补全括号的方法。

[ ( ( ) ) ] ( ( ) )

[ ( ) ( ) ] ( ) ( )

......

但是根据匹配规则,你会发现这玩意儿其实是合法的。也就是你并不用改它。


by imfkwk @ 2021-01-25 00:43:42

ac代码跑出来是这样[](([]))


by imfkwk @ 2021-01-25 00:47:22

哦,不。是从右括号开始往左找左括号。找到一个不匹配,那就不算。找不到也不算。


|