Postorder

Score: 58.12 (pass)

ahh, now *this* is golfable!

#!perl -l
$_=pop;for$x(pop=~/./g){s/(.*)$x(.*)/$1
$2
$x/}print//g

Score: 60.10 (fail)

This works on Win32, not on Linux. I think it's because of $^S but I don't know whether that disqualifies it. It's a bug in Perl 5.6.1, but not a consistent one...

#!perl
$_||=pop;$ARGV[0]=~/./g;s/$&/ /;do$0for split;print$&,$/x!$

Score: 63.15 (pass)

now non-recursive, and without the broken $^S

#!perl -l
$_=pop;s/(.*)($&)(.*)/$1
$3
$2/while$ARGV[0]=~/./g;print/./g

Score: 65.09 (pass)

back to the previous approach, looks more golfable

#!perl
$_||=pop;$ARGV[0]=~/./g;s/$&/ /;do$0for split;print$&,!caller&&$/

Score: 71.09 (pass)

#!perl -l
sub z{$ARGV[0]=~/./g;my$c=$&;(map$_?&z:'',split$c),$c}$_=pop;print z

Score: 78.09 (pass)

first time I've seen "caller" used in Perl Golf

#!perl -l
$t||=pop;$_||=pop;s/.//,$c=$&for$t;/$c/;do$0for$`,$';$o.=$&;caller||print$o

Score: 83.09 (pass)

too bad $& isn't localized *before* a match, that would make life easier...

#!perl -l
$t||=pop;$_||=pop;$a++;/@{[do{$t=~s#.##;$&}]}/;do$0for$`,$';$o.=$&;--$a||print$o

Score: 89.10 (pass)

#!perl -l
$_||=pop;$i=pop||$`||die;$a++;s/.//;$i=~s/$&//;do$0;{$'=~/$/;do$0}$o.=$&;--$a||print$o

Score: 98.10 (pass)

this one I like.

#!perl -l
$_=pop;sub d{my$i=pop;s/.//;$i=~/$&/;my($s,$t)=($&,$');d($`)if$`;d($t)if$t;$o.=$s}d pop;print$o