UVA 11988 Broken Keyboard (a.k.a. Beiju Text)

UVA_11988

    实际上在插入模式下，敲一个字符的时候就相当于在前一个字符与前一个字符的后一个字符中间插入了一个字符，于是可以用链表模拟插入的过程，最后再沿链表将各个字符输出即可。

#include<stdio.h>
#include<string.h>
#define MAXD 100010
int L[MAXD], R[MAXD];
char b[MAXD];
void solve()
{
    int i, j, k;
    L[0] = R[0] = 0;
    for(i = 1; b[i]; i ++)
    {
        if(b[i] == '[')
            L[i] = 0, R[i] = R[0];
        else if(b[i] == ']')
            L[i] = L[0], R[i] = 0;
        else
            L[i] = i - 1, R[i] = R[i - 1];
        L[R[i]] = i, R[L[i]] = i;
    }
    for(i = R[0]; i != 0; i = R[i]) if(b[i] != '[' && b[i] != ']') printf("%c", b[i]);
    printf("\n");
}
int main()
{
    while(gets(b + 1) != NULL)
        solve();
    return 0;    
}