【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==（链表）

Broken Keyboard

Description

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.

Samples

Input

This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

Output

BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

翻译一下：

你有一个破损的键盘。键盘上的所有键都可以正常工作，但有时Home键或者End键会自动按下。你并不知道键盘存在这一问题，而是专心地打稿子，甚至连显示器都没打开。当你打开显示器后，展现在你面前的是一段悲剧的文本。你的任务是再打开显示器之前计算出这段悲剧文本。

嗯，这道题是用链表做。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
int main()
{
    
	string s;
	while(cin>>s)
	{
    
		int len = s.size();
		s = '0'+s;
		int next[N]={
    0},last,pin;
		last = pin = 0;
		for(int i=1;i<=len;i++)
		{
    
			char ch=s[i];
			if(ch=='[')
				pin=0;
			else if(ch==']')
				pin=last;
			else
			{
    
				next[i]=next[pin];
				next[pin]=i;//这两句对应着思路4
				if(last == pin)
					last = i;
				pin = i;
			}
		}
		for(int i=next[0];i!=0;i=next[i])
			cout<<s[i];
		cout<<endl;	
	} 
}

Tip：Home键会让光标跳转到第一个字符之前，End键会让光标跳转到最后一个字符之后。

思路：

①我们要知道光标的位置用pin来记录。
②我们要知道末尾的字符位置用last来记录。
③当’['时光标跳转到最前面0的位置，当‘]’时光标跳转到末尾的位置last。
④在中间插入字符时，应该是：让该字符的next是前一个字符的next，并把前一个字符的next修改为该字符。（末尾的时候也可以这样，只不过该字符的next是0也就是结束）

我为什么要让字符串s变成‘0’+s呢……因为我要想输出这个链表，我就要有一个起始位置，但是我不知道我的起始位置是什么地方，所以我就假定了一个起始位置（位置0且不会改变），这样的话让字符串整体后退一个会更好操作。
==》（思路④的中间插入的思想可以用在末尾，但不能用在最前面，如果之前没有字符，那么他的next也就不存在，该字符也不能变成前一个字符的next,因此我们假定有一个不会改变的队首，输出的时候可以直接i = next[0]）