【UVA11988】破损的键盘

题目链接

维护一个链表，以及当前位置、head、tail的指针，模拟就行了

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

char s[100010];

int cnt,head,tail,pos;

struct Data{

	char c;

	int nxt;

} a[100010];

int main()

{

	while(scanf("%s",s)!=EOF){

		memset(a,0,sizeof(a));

		cnt=0;

		head=tail=pos=0;

		int n=strlen(s);

		for(int i=0;i<n;++i){

			if(s[i]=='[')

				pos=head;

			else if(s[i]==']')

				pos=tail;

			else{

				a[++cnt].nxt=a[pos].nxt;

				a[pos].nxt=cnt;

				a[cnt].c=s[i];

				if(pos==tail) tail=cnt;

				pos=cnt;

			}

		}

		head=a[head].nxt;

		while(head) putchar(a[head].c),head=a[head].nxt;

		puts("");

	}

	return 0;

}