BrokenKeyboard

It's clear that if you use array , you need shift O(n) number when you need insert a number. So we need use Chained List.

I use Structure to construct the chained list , and Code Quantity is large(code as follow):

#include<bits/stdc++.h>
//#define LOCAL
using namespace std;
/*
construct a chainedList for each line
for each chainlist:
1.joinable
2.insertable
*/
struct node{
    int data;
    node* next;
    node* pre; 
};

int c;
void print_line(node * h){
    node *p,*q;
    p=h->next,q=p->next;
    while(q!=NULL){
        printf("%c",p->data);
        p=q;
        q=q->next;
    }
}
    

int main(){
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    while(1){
        node* h = new node;
        node* e = new node;
        h->data=0,e->data=0;
        h->next=e,e->next=NULL,e->pre=h,h->pre=NULL;
        node *p,*q;
        p=h,q=e;
        while((c=getchar())!='\n' && c!=EOF){
            if (c=='['){
                p=h,q=h->next;
            }
            else if (c==']'){
                p=e->pre;
                q=e;
            }
            else{
                node* a = new node;
                a->data=c;
                p->next=a;
                a->pre=p;
                a->next=q;
                q->pre=a;
                p=a;
            }
        }
        print_line(h);
        if (c==EOF) break;
        printf("\n");
    }
    return 0;
}

As above , it's easy to understand ! However, it's low!

The answer in the book is that using the array and some marked symbols to construct the chained list.

#include<iostream>
#include<cstring>
//#define LOCAL
using namespace std;
int cl[100100];
int s[100100];
int cur=0,last=0;
int c=0,i=0;

int main(){
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    while(1){
        i=0;
        cl[0]=0;
        last=cur=0;
        while((c=getchar())!='\n' && c!=EOF){
            ++i;
            s[i]=c;
            if (c=='[') cur=0;
            else if (c==']') cur=last;
            else{
                cl[i]=cl[cur];
                cl[cur]=i;
                if (cur==last) last=i;
                cur=i;
            }
        }
        for (int i=cl[0];i!=0;i=cl[i]){
            printf("%c",(char) s[i]);
        }
        if (c==EOF) break;
        printf("\n");
    }
    return 0;
}

The second solution is a little difficult to understand , but it's a better solution and laconical !

And after all, I will use the second solution.