时间限制 内存限制
1000 ms 65536 KB

# 题目描述

Baymax 有一个破旧的键盘,键盘上所有的键都可以正常工作,但有时「Home」键或者「End」键会自动按下。Baymax 并不知道键盘的问题,而是专心地打着稿子,甚至连显示器都没打开。现在给出键盘的输入,请你计算出 Baymax 打开显示器之后显示的文本。

# 输入格式

不定组数据输入,保证数据组数不超过 5050 组。

每组数据一行,一个字符串 ss,保证 ss 的长度 100000≤100000,且 ss 中不含有空格。

其中,字符 [ 表示「Home」键,按下之后输入光标将移动到本行最前端;字符 ] 表示「End」键,按下之后输入光标将移动到本行最尾端。

# 输出格式

对于每组数据,输出一行,即显示器显示的文本。

# 输入样例

love[I_]_BUAA
[[]][][]Baymax_is_sad_for_the_broken_keyboard

# 输出样例

I_love_BUAA
Baymax_is_sad_for_the_broken_keyboard

# 样例解释

对于第一组数据,当遇到 [ 之前,输入 love ,文本为 love ,随后,光标移动到最前端,输入 I_ 后文本变为 I_love ,当遇到 ] 后,光标移动到文本末尾,输入 _BUAA ,最终输出文本为 I_love_BUAA

# 题解:链表

依题意,建一个链表模拟操作过程即可。

时间复杂度O(L)O(L),其中 LL 为所有字符串的长度之和。

参考代码:

#include <stdio.h>
#include <string.h>
int head, tail, size;
char str[100010];
struct Node
{
    int prev, next;
    char c;
} node[100010];
int Insert(int ind, char c)
{
    node[ ++ size].c = c;
    node[size].prev = ind, node[size].next = node[ind].next;
    node[node[ind].next].prev = size, node[ind].next = size;
    return size;
}
void print()
{
    int i = head;
    while (node[i].next != tail)
    {
        i = node[i].next;
        putchar(node[i].c);
    }
    puts("");
    return;
}
int main()
{
    // freopen("O.in", "r", stdin);
    // freopen("O.out", "w", stdout);
    while (~scanf("%s", str))
    {
        int len = strlen(str);
        head = 1, tail = 2, size = 2;
        node[head].next = tail, node[tail].prev = head;
        int ind = head;
        for (int i = 0; i < len; ++ i)
        {
            if (str[i] == '[')
                ind = head;
            else if (str[i] == ']')
                ind = node[tail].prev;
            else
                ind = Insert(ind, str[i]);
        }
        
        print();
    }
    return 0;
}