princepawn has asked for the wisdom of the Perl Monks concerning the following question:

I was in an interview today and the interviewer drew a bunch of binary op-trees on the board and said: "show me how you would process these." Since I had my trusty laptop with me, I said "can I write a program?" He said "sure."... so here is what I wrote. I would like to see this code optimized in terms of number of lines used. I am particularly keen on unifying my checks for simple versus complex right and left operands, in other words, the lines like 
if (ref($op_tree->[0]) eq 'ARRAY') {

[download]

It just occurred to me that some people might be thinking this would help me with my interview. But it won't the interview is over and I am just trying to improve my skills. 

use strict;


sub proc;
sub proc {
    my $op_tree = shift;
    if (ref($op_tree->[0]) eq 'ARRAY') {
        $op_tree->[0] = proc $op_tree->[0] ;
    }
    if (ref($op_tree->[2]) eq 'ARRAY') {
        $op_tree->[2] = proc $op_tree->[2] ;
    }

    my $expr = sprintf '%d %s %d', @$op_tree;
    warn "EXPR $expr";
    eval $expr;
}

my $sched1 = [ 1,       '||',   0 ];
my $sched2 = [ 1,       '&&',   0 ];
my $sched3 = [ $sched1, '&&',   1 ];
my $sched4 = [ $sched1, '&&',   $sched2 ];

warn proc $sched1;
warn proc $sched2;
warn proc $sched3;
warn proc $sched4;

[download]

Edit Masem 2001-11-13 - Small code fix

Replies are listed 'Best First'.
Re: optimizing a binary expression processor (revised)
by chip (Curate) on Nov 14, 2001 at 02:11 UTC
    How about a totally new approach: 

    sub proc {
    for (@_) { $_ = proc(@$_) if ref }
    warn "EXPR @_\n";
    eval "@_";
}

    [download]

        -- Chip Salzenberg, Free-Floating Agent of Chaos

[reply]
[d/l]
      Two complaints.

      The first is that you are editing the input data structure destructively, in place. I would far prefer to use a map statement rather than looping over @_ in place.

      The second is a complaint about eval's trapping of errors. Sometimes you want it, and sometimes you don't. With autogenerated code I generally don't. But as it stands I need to either live without (ie trust that your code works as it stands) or else catch your output, look at $@, and only then issue an error or else return the results. (And, of course, to do that right you need to propagate context.)

      Which is enough of a headache that I almost never see people do it. For instance in the above you use a warn for debugging. But if you had a large data structure, that trace would become unreadable, hence would be turned off. And then if you were passed a data structure that was wrong somewhere, little hint would be given as to where you had the problem. For instance consider: 

      print proc([2, '+', 2], '*', [3, '+']);

      [download]
[reply]
[d/l]
        WRT error checking: It's a fair cop. I was demonstrating the data structure usage.

        As for the destructiveness: It's a feature, not a bug: It avoids redundant evaluation of shared subexpressions.

            -- Chip Salzenberg, Free-Floating Agent of Chaos

[reply]
(tye)Re: optimizing a binary expression processor
by tye (Sage) on Nov 14, 2001 at 02:22 UTC 

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

my %op_code= (
    '||' => sub { $_[0] || $_[1] },
    '&&' => sub { $_[0] && $_[1] },
);

sub proc {
    my $op_tree = shift;
    return $op_tree   if  ! ref($op_tree);
    warn "EXPR @$op_tree";
    return $op_code{$op_tree->[1]}->(
        map proc($_), @{$op_tree}[0,2] );
}

my $sched1 = [ 1,       '||',   0 ];
my $sched2 = [ 1,       '&&',   0 ];
my $sched3 = [ $sched1, '&&',   1 ];
my $sched4 = [ $sched1, '&&',   $sched2 ];

warn proc $sched1;
warn proc $sched2;
warn proc $sched3;
warn proc $sched4;

    [download]

            - tye (but my friends call me "Tye")
[reply]
[d/l]

Back to Seekers of Perl Wisdom