Re: Convert stack-based code to "conventional" (was Re: Graphing SQLite's VDBE)

OK ... I've toyed around with the code and did a version with the extra parenthesis removal. Here ya go:

#!/usr/bin/perl -w
use strict;
use warnings;

my @stack = ();

sub binop {
        my $op = shift;
        my $prec = shift;

        my $lh = pop @stack;
        my ($lhop, $lhprec) = ($$lh[0], $$lh[1]);

        my $rh = pop @stack;
        my ($rhop, $rhprec) = ($$rh[0], $$rh[1]);

        # Wrap operand(s) with lower precedence
        $lhop = '(' . $lhop . ')' if $prec > $lhprec;
        $rhop = '(' . $rhop . ')' if $prec > $rhprec;

        push @stack, [ $lhop . $op . $rhop, $prec ];
}

while (<DATA>) {
        chomp;

        print "TOS='" . (@stack ? $stack[$#stack][0] : '-nil-') . "' "
        .       "stmt = '" . $_ . "'\n";

        my ($operator, $operand) = split;
        if ($operator eq 'push') {
                # A constant is atomic, so it has high precedence so
                # we don't wrap it
                push @stack, [$operand, 999];
        }
        elsif ($operator eq 'print') {
                my $op = pop @stack;
                my ($operand, $prec) = ($$op[0], $$op[1]);
                print "out: '" . $operand . "'\n";
        }
        elsif ($operator eq 'add') {
                binop '+', 1;
        }
        elsif ($operator eq 'mul') {
                binop '*', 2;
        }
}
__DATA__
push 3
push 5
add
push 7
push 9
add
mul
print
[download]

Which gives us:

root@swill ~/PerlMonks
$ ./stack_to_infix2.pl
TOS='-nil-' stmt = 'push 3'
TOS='3' stmt = 'push 5'
TOS='5' stmt = 'add'
TOS='5+3' stmt = 'push 7'
TOS='7' stmt = 'push 9'
TOS='9' stmt = 'add'
TOS='9+7' stmt = 'mul'
TOS='(9+7)*(5+3)' stmt = 'print'
out: '(9+7)*(5+3)'

root@swill ~/PerlMonks
$
[download]

--roboticus

P.S. I don't like my code for getting arguments off the stack, but all my attempts at simplifying it failed miserably. I'm sure it's something simple, but I haven't figured it out. What's a better way to do the following? (Or is my problem a bit earlier and I'm pushing the wrong thing on the stack?)

    my $op = pop @stack;
    my ($operand, $prec) = ($$op[0], $$op[1]);
[download]

Comment on Re: Convert stack-based code to "conventional" (was Re: Graphing SQLite's VDBE) Select or Download Code

Replies are listed 'Best First'.
Re^2: Convert stack-based code to "conventional" (was Re: Graphing SQLite's VDBE) by johngg (Canon) on Jan 24, 2007 at 15:35 UTC
How about `my ($operand, $prec) = map { $_->[0], $_->[1] } pop @stack;` [download] It seems to do what you want. Cheers, JohnGG	[reply] [d/l]
Re^2: Convert stack-based code to "conventional" (was Re: Graphing SQLite's VDBE) by roboticus (Chancellor) on Jan 25, 2007 at 03:24 UTC
OK ... now for a quick round of golf. Here's a version that's a bit tighter and easier to expand: #!/usr/bin/perl -w use strict; use warnings; my @stack = (); sub binop { my ($op, $prec) = @_; my ($rhop, $rhprec) = @{pop @stack}; my ($lhop, $lhprec) = @{pop @stack}; # Wrap operand(s) with lower precedence $lhop = '(' . $lhop . ')' if $prec > $lhprec; $rhop = '(' . $rhop . ')' if $prec > $rhprec; push @stack, [ $lhop . $op . $rhop, $prec ]; } my %handlers = ( 'push' => sub { push @stack, [shift, 999]; }, 'print' => sub { print "out: '" . ${@{pop @stack}}[0] . "'\n"; + }, 'add' => sub { binop '+', 1; }, 'mul' => sub { binop '', 2; } ); while (<DATA>) { chomp; print "TOS='" . (@stack ? $stack[$#stack][0] : '-nil-') . "' " . "stmt = '" . $_ . "'\n"; my ($operator, $operand) = split; if ($handlers{$operator}) { $handlers{$operator}->($operand); } else { print "Unknown operator: '$operator' for line '$_'\n"; } } __DATA__ push 3 push 5 add push apples add push oranges push 9 push bananas push peels mul add add mul print [download] Which gives us: TOS='-nil-' stmt = 'push 3' TOS='3' stmt = 'push 5' TOS='5' stmt = 'add' TOS='3+5' stmt = 'push apples' TOS='apples' stmt = 'add' TOS='3+5+apples' stmt = 'push oranges' TOS='oranges' stmt = 'push 9' TOS='9' stmt = 'push bananas' TOS='bananas' stmt = 'push peels' TOS='peels' stmt = 'mul' TOS='bananaspeels' stmt = 'add' TOS='9+bananaspeels' stmt = 'add' TOS='oranges+9+bananaspeels' stmt = 'mul' TOS='(3+5+apples)(oranges+9+bananaspeels)' stmt = 'print' out: '(3+5+apples)(oranges+9+bananaspeels)' [download] --roboticus	[reply] [d/l] [select]