| 时间限制 | 内存限制 | 
|---|---|
1000 ms | 
65536 KB | 
# 题目描述
Baymax 有一个破旧的键盘,键盘上所有的键都可以正常工作,但有时「Home」键或者「End」键会自动按下。Baymax 并不知道键盘的问题,而是专心地打着稿子,甚至连显示器都没打开。现在给出键盘的输入,请你计算出 Baymax 打开显示器之后显示的文本。
# 输入格式
不定组数据输入,保证数据组数不超过 组。
每组数据一行,一个字符串 ,保证 的长度 ,且 中不含有空格。
其中,字符  [  表示「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 。
# 题解:链表
依题意,建一个链表模拟操作过程即可。
时间复杂度:,其中 为所有字符串的长度之和。
参考代码:
#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;  | |
} |