尝试使用 Perl 在树中开发 PostFix 表示法

Question

我使用 Perl 遍历一棵树，然后使用内部节点作为运算符来计算树的叶节点。我希望能够以后缀方式打印它，并且我使用基本操作数相当容易地做到了这一点（只需在调用父节点之前分别调用左节点和右节点），但我在为平均函数。我在打印计算的实际结果时没有任何问题，但我希望能够以后缀表示法打印运算符和操作数。

例如，1 + Average(3, 4, 5) 将显示为 1 ； 3 4 5 平均+。

这是我的代码：

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->[0];

    # if a leaf, then the value is a number
    if ( $node_type eq 'leaf' ) {
        # base case
        my $value = $ex->[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->[1];
    my $left_ex = $ex->[2];
    my $right_ex = $ex->[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->[0];

    # if a leaf, then the value is a number
    if ( $node_type eq 'leaf' ) {
        # base case
        my $value = $ex->[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->[1];
    my $left_ex = $ex->[2];
    my $right_ex = $ex->[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;

这是一个测试：

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);

为了做到这一点，我意识到我必须更改子例程“Display”，但我不确定如何获取输出 -->价值价值； #表示未平均的值#值平均操作数等。

有什么想法吗？

Answer 1

我不能 100% 确定我理解你的问题，但这里是对你的两个函数的清理/改进：

my %ops = ( # dispatch table for operations
    average  => sub {my $acc; $acc += $_ for @_; $acc / @_},
    '+'      => sub {$_[0] + $_[1]},
    '-'      => sub {$_[0] - $_[1]},
    '*'      => sub {$_[0] * $_[1]},
    'mod'    => sub {$_[0] % $_[1]},
    (map {$_ => sub {$_[1] ? $_[0] / $_[1] : undef}} qw (/ div)),
);
sub Evaluate {
    my $ex = shift;
    print "evaluating: ", Dumper($ex), "\n" if $debug;

    my $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";
    }

    my $operation = $ex->[1];
    my @values    = map {Evaluate($_)} @$ex[2 .. $#$ex];

    defined or return for @values;

    if (my $op = $ops{$operation}) {
        return $op->(@values);
    } else {
        print "operation $operation not found\n";
        return undef;
    }
}

这里大的 if/elsif 块被替换为调度表。这允许您将逻辑与解析器分开。我还用 @values 数组替换了 $left_value 和 $right_value 变量，允许您的代码扩展到 n 元操作（例如平均）。

以下 Display 函数也已更新，可以处理 n 元操作：

my %is_infix = map {$_ => 1} qw( * + / - );
sub Display {
    my ($ex, $style) = @_;

    my $node_type = $ex->[0];

    # if a leaf, then the value is a number
    if ( $node_type eq 'leaf' ) {
        return $ex[1];
    }

    # 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 n arguments
    my $operation = $ex->[1];

    if ($style and $style eq 'infix') {
        my @values = map {Display($_, $style)} @$ex[2 .. $#$ex];
        if ($is_infix{$operation}) {
            return "$values[0] $operation $values[1]"
        } else {
            local $" = ', ';                 # "
            return "$operation( @values )"
        }
    } else { # postfix by default
        my @out;
        for (@$ex[2 .. $#$ex]) {
            if (@out and $_->[0] eq 'internal') {
                push @out, ';'
            }
            push @out, Display($_, $style)
        }
        return join ' ' => @out, $operation;
    }
}

您可以将 Display 调用为 Display($tree) 或 Display($tree, 'postfix') 用于后缀表示法。和 Display($tree, 'infix') 用于中缀表示法。

ex1 is 42
ex1: 42
ex1: 42

ex2 is 52
ex2: 42 10 +
ex2: 42 + 10

ex3 is 26.5
ex3: 42 10 + 1 average
ex3: average( 42 + 10, 1 )

我相信这就是您正在寻找的。

最后，使用第一个示例 1 +average(3, 4, 5):

my $avg = ['internal', 'average', [leaf => 3], [leaf => 4], [leaf => 5] ];
my $ex4 = ['internal', '+', [leaf => 1], $avg ];

print "ex4 is ", Evaluate($ex4), "\n";
print "ex4: ", Display($ex4), "\n";
print "ex4: ", Display($ex4, 'infix'), "\n";
print "\n";

打印：

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

Answer 2

也许尝试AlgebraicToRPN？