题解 P1241 【括号序列】

寒冰大大 · 2020-03-26 18:38:20 · 题解

貌似就是一个很普通的栈。 按照题目的说法 ~[~(~]~) 是不行的 另外题目有个很重要的条件

找到在它左边最靠近它的左括号匹配

也就是说[(]这种要被补成[]()[] 而[)]要被补成[()]

接下来就只要用一下pair和一个标记数组就可以了。

#include<touwenjian.h>
using namespace std;

using namespace std;

stack <pair<int,int> > s1;
char s[200];
int bj[200],n;

int main()
{
    scanf("%s",s);
    memset(bj,-1,sizeof(bj));  //后面认为匹配的()在bj中体现是1，[]是2，所以赋为其他值
    int i,j;
    n=strlen(s);
    for(i=0;i<n;i++)
    {
        char t=s[i];
        if(t=='('||t=='[') s1.push(make_pair(i,t=='('));
        if(t==')'||t==']') if(s1.empty()||s1.top().second!=(t==')')) bj[i]=(t==')'); else s1.pop();
    }
    while(!s1.empty()) bj[s1.top().first]=s1.top().second,s1.pop();
    for(i=0;i<n;i++)
    {
        if(bj[i]==-1) printf("%c",s[i]);
        else if(bj[i]==1) printf("()");
        else printf("[]");
    }
    return 0;
}