[exercise-4] (UVA 11988) broken keyboard = = (linked list)

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

Translate ：

You have a broken keyboard . All keys on the keyboard work properly , But sometimes Home Key or End The key will be pressed automatically . You didn't know there was a problem with keyboards , But concentrate on typing , I didn't even turn on the monitor . When you turn on the monitor , In front of you is a tragic text . Your task is to calculate this tragic text before turning on the monitor again .

Um. , This problem is done with a linked list .

AC Code ：

#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;// These two sentences correspond to the train of thought 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 The key will make the cursor jump to the front of the first character ,End Key will make the cursor jump after the last character .

Ideas ：

① We need to know the position of the cursor with pin To record .
② We need to know that the position of the last character is last To record .
③ When ’[' The timeline jumps to the front 0 The location of , When ‘]’ The chronometer jumps to the end last.
④ When inserting characters in the middle , Should be ： Let the next Is the previous character next, And put the previous character next Change to this character .（ This can also be done at the end , It's just the character next yes 0 That's the end ）

Why should I make strings s become ‘0’+s Well …… Because I want to output this linked list , I will have a starting position , But I don't know where I start , So I assumed a starting position （ Location 0 And it won't change ）, In this case, it will be better to retreat the whole string by one .
==》（ Ideas ④ The idea of inserting in the middle of can be used at the end , But it can't be used in the front , If there are no characters before , So his next There is no such thing as , This character cannot become the character of the previous character next, So we assume that there is a team leader who will not change , When outputting, you can directly i = next[0]）