Trying to Develop PostFix Notation in Tree Using Perl -

i'm using perl run through tree, , calculate leaf nodes of tree using internal nodes operators. want able print in postfix manner, , managed this basic operands (simply call left , right nodes respectively before calling parent) having trouble producing desired output average function. don't have trouble printing actual result of calculation, want able print operators , operands in postfix notation.

for example, 1 + average(3, 4, 5) shown 1 ; 3 4 5 average +.

here code:

use strict; use warnings;  use data::dumper;  $data::dumper::indent = 0; $data::dumper::terse = 1;  $debug = 0;  # arithmetic expression tree reference list, can # of 2 kinds follows: #    [ 'leaf', value ] #    [ 'internal', operation, leftarg, rightarg ]  # evaluate($ex) takes arithmetic expression tree , returns  # evaluated value.  sub evaluate {     ($ex) = @_;      $debug ,         print "evaluating: ", dumper($ex), "\n";      # kind of node given in first element of array     $node_type = $ex->[0];      # if leaf, value number     if ( $node_type eq 'leaf' ) {         # base case         $value = $ex->[1];         $debug ,             print "returning leaf: $value\n";         return $value;                     }      # if not leaf, internal,      if ( $node_type ne 'internal' ) {         die "eval: strange node type '$node_type' when evaluating tree";     }      # should have operation , 2 arguments     $operation = $ex->[1];     $left_ex = $ex->[2];     $right_ex = $ex->[3];      # evaluate left , right arguments;     $left_value = evaluate($left_ex);     $right_value = evaluate($right_ex);      # if arguments undefined, our value undefined.     return undef unless          defined($left_value) , defined($right_value);      $result;      # or explicitly required operators ...     if ($operation eq 'average') {         $result = ($left_value + $right_value) / 2;     }     if ($operation eq '+') {         $result = $left_value + $right_value;     } elsif ($operation eq '-') {         $result = $left_value - $right_value;     } elsif ($operation eq '*') {         $result = $left_value * $right_value;     } elsif ($operation eq 'div') {         if ($right_value != 0 ) {         $result = int ($left_value / $right_value);         } else {             $result = undef;         }     } elsif ($operation eq 'mod') {         $result = $left_value % $right_value;     } elsif ($operation eq '/') {         if ( $right_value != 0 ) {             $result = $left_value / $right_value;             }         else {             $result = undef;             }     }      $debug ,         print "returning '$operation' on $left_value , $right_value result: $result\n";      return $result;     }   # display($ex, $style) takes arithmetic expression tree , style  # parameter ('infix' or 'postfix') , returns string represents  # printable form of expression in given style.  sub display {     ($ex, $style) = @_;      # kind of node given in first element of array     $node_type = $ex->[0];      # if leaf, value number     if ( $node_type eq 'leaf' ) {         # base case         $value = $ex->[1];         return $value;                     }      # if not leaf, internal,      if ( $node_type ne 'internal' ) {         die "display: strange node type '$node_type' when evaluating tree";     }      # should have operation , 2 arguments     $operation = $ex->[1];     $left_ex = $ex->[2];     $right_ex = $ex->[3];      # evaluate left , right arguments;     $left_value = display($left_ex, $style);     $right_value = display($right_ex, $style);      $result;     if ($operation ne 'average') {     $result = "($left_value $operation $right_value) \n $left_value $right_value $operation";     } else {     $result = "($left_value $operation $right_value) \n $left_value $right_value $operation";     }     return $result;     }  # module end; 1; 

and here test:

use strict; use warnings;  use display;  use arith;  $ex1 = [ 'leaf', 42];  $ex2 = [ 'internal', '+', [ 'leaf', 42], [ 'leaf', 10 ] ];  $ex3 = [ 'internal', 'average', $ex2, [ 'leaf', 1 ] ];    print "ex1 ", evaluate($ex1), "\n"; print "ex1: ", display($ex1), "\n"; print "\n";  print "ex2 ", evaluate($ex2), "\n"; print "ex2: ", display($ex2), "\n"; print "\n";  print "ex3 ", evaluate($ex3), "\n"; print "ex3: ", display($ex3), "\n"; print "\n"; display::render(\$ex3); 

in order this, realize have change subroutine "display", i'm not sure how output --> value value ; #to indicate values aren't averaged# value value average operand etc.

any ideas?

i not 100% sure understand problem, here cleanup / improvement of 2 functions:

my %ops = ( # dispatch table operations     average  => sub {my $acc; $acc += $_ @_; $acc / @_},     '+'      => sub {$_[0] + $_[1]},     '-'      => sub {$_[0] - $_[1]},     '*'      => sub {$_[0] * $_[1]},     'mod'    => sub {$_[0] % $_[1]},     (map {$_ => sub {$_[1] ? $_[0] / $_[1] : undef}} qw (/ div)), ); sub evaluate {     $ex = shift;     print "evaluating: ", dumper($ex), "\n" if $debug;      $node_type = $ex->[0];     if ( $node_type eq 'leaf' ) {         print "returning leaf: $$ex[1]\n" if $debug;         return $$ex[1];     }     elsif ( $node_type ne 'internal' ) {         die "eval: strange node type '$node_type' when evaluating tree";     }      $operation = $ex->[1];     @values    = map {evaluate($_)} @$ex[2 .. $#$ex];      defined or return @values;      if (my $op = $ops{$operation}) {         return $op->(@values);     } else {         print "operation $operation not found\n";         return undef;     } } 

here large if/elsif block replaced dispatch table. allows separate logic parser. have replaced $left_value , $right_value variables @values array, allowing code scale n-arity operations (like average).

the following display function has been updated handle n-arity operations:

my %is_infix = map {$_ => 1} qw( * + / - ); sub display {     ($ex, $style) = @_;      $node_type = $ex->[0];      # if leaf, value number     if ( $node_type eq 'leaf' ) {         return $$ex[1];     }      # if not leaf, internal,     if ( $node_type ne 'internal' ) {         die "display: strange node type '$node_type' when evaluating tree";     }      # should have operation , n arguments     $operation = $ex->[1];      if ($style , $style eq 'infix') {         @values = map {display($_, $style)} @$ex[2 .. $#$ex];         if ($is_infix{$operation}) {             return "$values[0] $operation $values[1]"         } else {             local $" = ', ';                 # "             return "$operation( @values )"         }     } else { # postfix default         @out;         (@$ex[2 .. $#$ex]) {             if (@out , $_->[0] eq 'internal') {                 push @out, ';'             }             push @out, display($_, $style)         }         return join ' ' => @out, $operation;     } } 

you can call display display($tree) or display($tree, 'postfix') postfix notation. , display($tree, 'infix') infix notation.

 ex1 42 ex1: 42 ex1: 42  ex2 52 ex2: 42 10 + ex2: 42 + 10  ex3 26.5 ex3: 42 10 + 1 average ex3: average( 42 + 10, 1 ) 

which believe looking for.

finally, using first example 1 + average(3, 4, 5):

my $avg = ['internal', 'average', [leaf => 3], [leaf => 4], [leaf => 5] ]; $ex4 = ['internal', '+', [leaf => 1], $avg ];  print "ex4 ", evaluate($ex4), "\n"; print "ex4: ", display($ex4), "\n"; print "ex4: ", display($ex4, 'infix'), "\n"; print "\n"; 

which prints:

 ex4 5 ex4: 1 ; 3 4 5 average + ex4: 1 + average( 3, 4, 5 )