UVa 11988 悲剧文本（四种方法）

题目链接

You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed (internally). You’re not aware of this issue, since you’re focusing on the text and did not even turn on the monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor).In Chinese, we can call it Beiju. Your task is to find the Beiju text.

Input
There are several test cases. Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters ‘[’ and ‘]’. ‘[’ means the “Home” key is pressed internally, and ‘]’ means the “End” key is pressed internally. The input is terminated by end-of-file (EOF).

Output
For each case, print the Beiju text on the screen.

题目大意：当你输入一段文本时（回车代表结束），每当输入了’[‘字符代表按下了键盘上的home键（即接下来的输入会显示在文本头），每当输入’['字符代表按下end键（即光标跳到文本尾部），求真实显示出的文本

1.第一眼看到题目时脑海中想着字符串的操作，至于文本头那里直接用栈处理，碰到回车一次性出栈即可，也过了。然后翻开书看LRJ老师的代码，看了几遍没有眉目，于是自己在纸上简单模拟了两遍，稍微看出来一点头目，但又不是那么地清晰。看到了方法是数组模拟链表，想到我大一上学的链表都忘的差不多了，于是乎，看书看博客的苦逼生活

2.学会链表之后，又去学了一下数组模拟链表，很快掌握了其中的原理。由于其他人的模板在我看来并不好用，顺便先写了个单向链表的博客总结，有疑问的小伙伴可以去看一下。接下来看LRJ老师的代码，一下子就看懂了！

3.还没结束，由于刚刚复习链表，自己按链表的指针形式去写这道题（PS：真的是很容易错，写完还要花大量时间调试）。在调试的过程中遇到了死循环，请教了实验室WZQ大佬，于是讨论这道题的时候又掌握了一种方法（方法四），这道题花了挺长时间，收获也蛮大。

2019就剩一个月零几天了，冲啊，奥利给！！！

方法一（string+stack）

就是字符串的模拟，挺好理解的

#include <iostream>
#include <stack>
#include <string>
using namespace std;
stack<string> s;
int main(){
    string s1,s2;
    while(cin>>s1){
        string ans="",res="";
        for(int i=0;i<s1.size();i++){
            if(s1[i]=='['){
                s2="";
                i++;
                while(i<s1.size()&&s1[i]!='['&&s1[i]!=']'){
                    s2+=s1[i];
                    i++;
                }
                s.push(s2);
                if(s1[i]=='[') i--;
            }else if(s1[i]==']')
                continue;
            else ans+=s1[i];
        }
        while(!s.empty()){
            res+=s.top();
            s.pop();
        }
        res+=ans;
        cout<<res<<endl;
    }
    return 0;
}

方法二（LRJ老师方法，强烈建议掌握）

如果不懂数组是如何模拟链表的，可参考下面博客

#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
int last,cur,next1[maxn];   ///C++的next是关键字，要更改名字
char s[maxn];
int main(){
    while(scanf("%s",s+1)!=EOF){
        int n=strlen(s+1);
        last=cur=0;
        next1[0]=0;
        for(int i=1;i<=n;i++){
            char ch=s[i];
            if(ch=='[') cur=0;  ///光标移向下标0,这之后输入的数都会接替储存下标1,2...相反之前的前几个数储存这几个数的下标
            else if(ch==']') cur=last;  ///原理同上
            else{
                ///参考数组模拟链表的赋值方式
                next1[i]=next1[cur];
                next1[cur]=i;
                if(cur==last) last=i;
                cur=i;
            }
        }
        for(int i=next1[0];i!=0;i=next1[i]){ ///参考数组模拟链表的遍历方式
            printf("%c",s[i]);
        }
        printf("\n");
    }
    return  0;
}

方法三（指针链表）

有一说一，指针的链表确实很容易把人绕晕，下面的代码调试了好久没成功。但是这也是笔者认为可行的一种办法：写两个链表，一个链表用来维护主链表，另一个用来维护碰到home键的子链表，每当退出一个home后将两个链表首尾相连，子链表在前，同时更新主链表的head。
下面的代码可以通过几个样例例如样例一和"I[am[a]good]boy"，但是样例二进入了死循环，一直没搞懂~
欢迎dalao指出错误

有错的代码：

#include <iostream>
#include <malloc.h>
using namespace std;
typedef struct node{
    char a;
    struct node* next;
}Node;
void show(Node *list){
    Node *t=list;
    while(t->next!=nullptr){
        t=t->next;
        printf("%c",t->a);
    }
    printf("\n");
}
Node *init(char c){ //创建一个n个元素的链表
    Node *head,*div,*end;
    char ch;
    head=(Node *)malloc(sizeof(Node));
    end=head;
    if(c!='['&&c!=']'){
        div=(Node *)malloc(sizeof(Node));
        div->a=c;
        end->next=div;
        end=div;
    }
    while(1){
        ch=getchar();
        loop2: if(ch=='\n') break;
        else if(ch=='['){
            loop: Node *h,*d,*e;
            h=(Node *)malloc(sizeof(Node));
            e=h;
            while(ch=getchar()){
                if(ch=='['){
                    if(head->next!=nullptr){
                        e->next=head->next;
                    }else end=h;
                    head=h;
                    goto loop;
                }else if(ch==']'){
                    if(head->next!=nullptr){
                        e->next=head->next;
                    }else end=h;
                    head=h;
                    break;
                }else if(ch=='\n'){
                    if(head->next!=nullptr){
                        e->next=head->next;
                    }else end=h;
                    head=h;
                    goto loop2;
                }else{
                    d=(Node *)malloc(sizeof(Node));
                    d->a=ch;
                    e->next=d;
                    e=d;
                }
            }
            continue;
        }else if(ch==']') continue;
        div=(Node *)malloc(sizeof(Node));
        div->a=ch;
        end->next=div;
        end=div;
    }
    end->next=nullptr;
    return head;
}
void freeMemory(Node *list){
    Node *t=list;
    while(list->next!=nullptr){
        t=list;
        list=t->next;
        free(t);
    }
    free(list);
}
int main()
{
    char c;
    while(c=getchar()){
        if(c!='\n'){
            Node *head=init(c);
            show(head);
            freeMemory(head);
        }
    }
    return 0;
}

方法四（字符串处理）

仔细看就会发现，这是和栈的思路是一样的，代码也是类似的，就是用两个串来维护home和主字符串。但是贼坑的是明明和方法一几乎一样，但是就是TLE，很无奈，之前用getchar()也是TLE。不管了，也许就是UVA的OJ有点LJ。我觉得代码是没问题的！

TLE代码:

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s,s1="",s2;
    while(cin>>s){
        for(int i=0;i<s.size();i++){
            if(s[i]=='['){
                s2="";
                for(i++;i<s.size();++i){
                    if(s[i]=='['||s[i]==']'){
                        s1=s2+s1;
                        s2="";
                        break;
                    }else s2+=s[i];
                }
                if(s[i]=='[') i--;
            }else if(s[i]==']') continue;
            else s1+=s[i];
        }
        cout<<s1<<endl;
        s1="";
    }
    return 0;
}