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). The size of input file does not exceed 5MB.
Output
For each case, print the Beiju text on the screen.
Sample Input
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
Sample Input
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University
题目类型：单向循环链表
算法分析：将字符串一行读入，逐个判断字符，如果字符是’[’，就将当前位置指针置为0，如果字符是’]’，就将当前位置指针置为尾指针指向的位置。如果字符是其他字符，就将该字符插入到当前指针所指向的字符位置的后一个，并更新当前指针，如果插入的位置是最后一个位置，则更新尾指针
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <fstream> #include <cstring> using namespace std; const int maxn = 100000 + 166; char input[maxn]; int Next[maxn]; int main() { // ifstream cin ("aaa.txt"); int last, cur; while (cin >> (input + 1)) { int len = strlen (input + 1); Next[0] = 0; cur = last = 0; int i; for (i = 1; i <= len; i++) { if (input[i] == ']') cur = last; else if (input[i] == '[') cur = 0; else { Next[i] = Next[cur]; Next[cur] = i; if (cur == last) last = i; cur = i; } } for (i = Next[0]; i; i = Next[i]) cout << input[i]; cout << endl; } return 0; } |
- « 上一篇：uva11424
- uva12100：下一篇 »