POJ 3367 Expressions

問題

アルファベットの小文字であらわされる数値および、アルファベットの大文字であらわされる演算子からなる式が与えられる。

ただし式は後置記法になっていて、
abOは、

• スタックにaを積む
• スタックにbを積む
• スタックからa,bを取り出し、スタックにb O aを積む

という風に処理される。

上の処理において、スタックの代わりにキューを使ったときに、
元の式として解釈される文字列を求めよ。

制約条件

テストケースの数≦200
文字列の長さ≦10000

方針

文字列を深さ優先探索で構文解析して、構文木を作る。
構文木に対して、幅優先探索をして出力される文字列が、求める文字列である。
（ただし前後逆になっているので、ひっくりかえす）

木の作り方は、深さ優先探索しながらポインタを貼ってく感じ。
（上手く説明しにくい……）

幅優先探索は普通にキューを使ってやればいい。
下のコードではキューは手作り。
今学習中の蟻本が、毎回キューを手作りしてるのでちょっとそのせい。

ソースコード

int n, len;
char in[10001],ans[10001];
int p,lch[10001],rch[10001];
int q[10001];

void parse(){
	int cur=p;
	if(isupper(in[cur])){
		rch[cur]=--p;
		parse();
		lch[cur]=p;
		parse();
	}
	else lch[cur]=rch[cur]=-1, p--;
}
int main()
{
	scanf("%d ",&n);
	while(n--){
		gets(in);
		len=strlen(in);
		p=len-1;
		parse();
		
		int s=0,t=0;
		ans[len]=0;
		q[t++]=len-1;
		while(s<t){
			ans[--len]=in[q[s]];
			if(lch[q[s]]>=0)q[t++]=lch[q[s]];
			if(rch[q[s]]>=0)q[t++]=rch[q[s]];
			s++;
		}
		puts(ans);
	}
	return 0;
}