Postorder

Score: 48.12 (fail)

looks like a solution for factorial actually

#!perl -l
$_*=$z%9e9,/0*$/,$z=$`for++$z..pop;print$z%10

Score: 51.10 (pass)

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

Score: 56.11 (pass)

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

Score: 57.09 (pass)

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

Score: 60.10 (pass)

WOW, finally some real results...

#!perl
$_=pop;for$c(pop=~/./g){s/$c(\w*)/-$1-$c/;}s/-//g;print$_,$/

Score: 86.14 (fail)

#!perl
($_=pop)&&(/~/?$x.=$`:($ARGV[0]=~/./g,/$&/,push@ARGV,"$&~",$',$`))while$=--;print$x,$/

Score: 87.10 (pass)

#!perl
$_=pop;($~=pop)=~/../?/./g+$~=~/$&/

Score: 100.11 (pass)

#!perl
($P,$I)=@ARGV;sub z{$P=~s/.//;$~=~/$&/;my$b=$';my$v=$&;&z if$~=$`;&z if$~=$b;print$v}$~=$I;z;print$/

Score: 120.14 (pass)

#!perl
sub p{my($i,$p)=@_;$i=$1,@_=($4,substr$p,1+length$3),p($3,$2).&p.$i if"$p!$i"=~/(.)(.*)!(.*)\1(.*)/}print p(@ARGV)."\n";

Score: 134.11 (pass)

#!perl
sub p{my($i,$p)=@_;"$p!$i"=~/(.)(.*)!(.*?)\1(.*)/||return;my$z=$1;my@x=($4,substr$p,1+length$3);p($3,$2).p(@x).$z}print p(@ARGV)."\n";

Score: 161.11 (pass)

#!perl
sub p{my($i,$p)=@_;return if!$p;$_[1]=~/(.)/;my$z=$1;$i=~/(.*?)$z(.*)/;my$x=$2;$l=$+[1];my$y=substr($p,$l+1);p($1,substr$p,1,$l).p($x,$y).$z}print p(@ARGV)."\n";