Shunting-yard algorithm
my %prec =
'^' => 4,
'*' => 3,
'/' => 3,
'+' => 2,
'-' => 2,
'(' => 1;
my %assoc =
'^' => 'right',
'*' => 'left',
'/' => 'left',
'+' => 'left',
'-' => 'left';
sub shunting-yard ($prog) {
my @inp = $prog.words;
my @ops;
my @res;
sub report($op) { printf "%25s %-7s %10s %s\n", ~@res, ~@ops, $op, ~@inp }
sub shift($t) { report( "shift $t"); @ops.push: $t }
sub reduce($t) { report("reduce $t"); @res.push: $t }
while @inp {
given @inp.shift {
when /\d/ { reduce $_ };
when '(' { shift $_ }
when ')' { while @ops and (my $x = @ops.pop and $x ne '(') { reduce $x } }
default {
my $newprec = %prec{$_};
while @ops {
my $oldprec = %prec{@ops[*-1]};
last if $newprec > $oldprec;
last if $newprec == $oldprec and %assoc{$_} eq 'right';
reduce @ops.pop;
}
shift $_;
}
}
}
reduce @ops.pop while @ops;
@res;
}
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
Output:
reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 shift + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 + reduce 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 4 + shift * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 4 + * reduce 2 / ( 1 - 5 ) ^ 2 ^ 3
3 4 2 + reduce * ( 1 - 5 ) ^ 2 ^ 3
3 4 2 * + shift / ( 1 - 5 ) ^ 2 ^ 3
3 4 2 * + / shift ( 1 - 5 ) ^ 2 ^ 3
3 4 2 * + / ( reduce 1 - 5 ) ^ 2 ^ 3
3 4 2 * 1 + / ( shift - 5 ) ^ 2 ^ 3
3 4 2 * 1 + / ( - reduce 5 ) ^ 2 ^ 3
3 4 2 * 1 5 + / ( reduce - ^ 2 ^ 3
3 4 2 * 1 5 - + / shift ^ 2 ^ 3
3 4 2 * 1 5 - + / ^ reduce 2 ^ 3
3 4 2 * 1 5 - 2 + / ^ shift ^ 3
3 4 2 * 1 5 - 2 + / ^ ^ reduce 3
3 4 2 * 1 5 - 2 3 + / ^ reduce ^
3 4 2 * 1 5 - 2 3 ^ + / reduce ^
3 4 2 * 1 5 - 2 3 ^ ^ + reduce /
3 4 2 * 1 5 - 2 3 ^ ^ / reduce +
3 4 2 * 1 5 - 2 3 ^ ^ / +
Last updated