title: Trying to Develop PostFix Notation in Tree Using Perl
body: <p>I'm using Perl to run through a tree, and then calculate the leaf nodes of the tree using the internal nodes as operators. I want to be able to print this in a postfix manner, and I managed to this this fairly easily with the basic operands (simply call the left and right nodes respectively before calling the parent) but I am having trouble producing the desired output for an average function. I don't have any trouble printing the actual result of the calculation, but I want to be able to print the operators and operands in postfix notation.</p>
  
  <p>For example, 1 + average(3, 4, 5) will be shown as 1 ; 3 4 5 average +. </p>
  
  <p>Here is my code:</p>
  
  <pre><code>use strict;
  use warnings;
  
  use Data::Dumper;
  
  $Data::Dumper::Indent = 0;
  $Data::Dumper::Terse = 1;
  
  my $debug = 0;
  
  # an arithmetic expression tree is a reference to a list, which can
  # be of two kinds as follows:
  #    [ 'leaf', value ]
  #    [ 'internal', operation, leftarg, rightarg ]
  
  # Evaluate($ex) takes an arithmetic expression tree and returns its 
  # evaluated value.
  
  sub Evaluate {
      my ($ex) = @_;
  
      $debug and
          print "evaluating: ", Dumper($ex), "\n";
  
      # the kind of node is given in the first element of the array
      my $node_type = $ex-&gt;[0];
  
      # if a leaf, then the value is a number
      if ( $node_type eq 'leaf' ) {
          # base case
          my $value = $ex-&gt;[1];
          $debug and
              print "returning leaf: $value\n";
          return $value;            
          }
  
      # if not a leaf, then is internal,
  
      if ( $node_type ne 'internal' ) {
          die "Eval: Strange node type '$node_type' when evaluating tree";
      }
  
      # should now have an operation and two arguments
      my $operation = $ex-&gt;[1];
      my $left_ex = $ex-&gt;[2];
      my $right_ex = $ex-&gt;[3];
  
      # evaluate the left and right arguments;
      my $left_value = Evaluate($left_ex);
      my $right_value = Evaluate($right_ex);
  
      # if any arguments are undefined, our value is undefined.
      return undef unless 
          defined($left_value) and defined($right_value);
  
      my $result;
  
      # or do it explicitly for the 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 and
          print "returning '$operation' on $left_value and $right_value result: $result\n";
  
      return $result;
      }
  
  
  # Display($ex, $style) takes an arithmetic expression tree and a style 
  # parameter ('infix' or 'postfix') and returns a string that represents 
  # printable form of the expression in the given style.
  
  sub Display {
      my ($ex, $style) = @_;
  
      # the kind of node is given in the first element of the array
      my $node_type = $ex-&gt;[0];
  
      # if a leaf, then the value is a number
      if ( $node_type eq 'leaf' ) {
          # base case
          my $value = $ex-&gt;[1];
          return $value;            
          }
  
      # if not a leaf, then is internal,
  
      if ( $node_type ne 'internal' ) {
          die "Display: Strange node type '$node_type' when evaluating tree";
      }
  
      # should now have an operation and two arguments
      my $operation = $ex-&gt;[1];
      my $left_ex = $ex-&gt;[2];
      my $right_ex = $ex-&gt;[3];
  
      # evaluate the left and right arguments;
      my $left_value = Display($left_ex, $style);
      my $right_value = Display($right_ex, $style);
  
      my $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;
  </code></pre>
  
  <p>And here is a test:</p>
  
  <pre><code>use strict;
  use warnings;
  
  use Display;
  
  use arith;
  
  my $ex1 = [ 'leaf', 42];
  
  my $ex2 = [ 'internal', '+', [ 'leaf', 42], [ 'leaf', 10 ] ];
  
  my $ex3 = [ 'internal', 'average', $ex2, [ 'leaf', 1 ] ];
  
  
  
  print "ex1 is ", Evaluate($ex1), "\n";
  print "ex1: ", Display($ex1), "\n";
  print "\n";
  
  print "ex2 is ", Evaluate($ex2), "\n";
  print "ex2: ", Display($ex2), "\n";
  print "\n";
  
  print "ex3 is ", Evaluate($ex3), "\n";
  print "ex3: ", Display($ex3), "\n";
  print "\n";
  Display::Render(\$ex3);
  </code></pre>
  
  <p>In order to do this, I realize I will have to change the subroutine "Display", but I'm not sure how to get the output --> value value ; #to indicate values that aren't averaged# value value average operand etc.</p>
  
  <p>Any ideas?</p>