确定树木是否"平等"

Question

我正在使用Perl,我需要确定两个算术表达式树是否"相等".平等,我的意思是树的形状是相等的,而不是其中的特定值.所以,例如['internal',' - '['leaf',5] ['leaf',4]]与['internal','average',['internal','+', ['leaf',42],['leaf',10]],['leaf',1]],但与['internal','+'['leaf',3] ['leaf'相同,20]].所以,我只是想匹配形状.我有一个子程序,我希望能够做到这一点,但到目前为止,我无法使其正确匹配.这是子程序:

sub isEqualShape {
    my ($ex1, $ex2) = @_;
    my $node_type = $ex1->[0];
    my $node_type2= $ex2->[0];
    my $check;
    foreach (@$ex1){
        if ( $node_type eq 'leaf' && $node_type2 eq 'leaf'){
            $check = 1;
        }
        elsif ($node_type eq 'internal' && $node_type2 eq 'internal'){
            $check = 1;
        }
        else {
            $check = 0;
            return 0;
            last;
        }
    }
    foreach (@$ex2){
        if ( $node_type eq 'leaf' && $node_type2 eq 'leaf'){
            $check = 1;
        }
        elsif ($node_type eq 'internal' && $node_type2 eq 'internal'){
            $check = 1;
        }
        else {
            $check = 0;
            return 0;
            last;
        }  
    }
    return $check;
}

这是我的测试文件:

my $ex1 = [ 'leaf', 42];

my $ex2 = [ 'internal', '+', [ 'leaf', 42], [ 'leaf', 10 ] ];

my $ex3 = [ 'internal', 'average', $ex2, [ 'leaf', 1 ] ];

my $tree = isEqualShape($ex2, $ex3);
if ($tree eq '1'){
    print "Shapes Are Equal\n";
}
else {
    print "Shapes Are Not Equal \n";
}

当比较ex1与ex2或ex3之间时,这将返回Shapes is Not Equal,就像它应该的那样.但是,当比较ex2或ex3时,它返回的形状是相等的.我该如何解决这个问题,并且可能会使其更具普遍性？

编辑:我也尝试过从数组中使用弹出,但是这会导致引用错误(我对整个参考文件都不熟悉).

sub isEqualShape {
    my @array = @_;
    my ($ex1, $ex2) = @array;
    my $node_type = $ex1->[0];
    my $node_type2= $ex2->[0];
    my $check;
    foreach (@$ex1){
        if ( $node_type eq 'leaf' && $node_type2 eq 'leaf'){
            $check = 1;
        }
        elsif ($node_type eq 'internal' && $node_type2 eq 'internal'){
            $check = 1;
        }
        else {
            $check = 0;
            return 0;
            last;
        }
    }
    for (@$ex2){
        if ( $node_type eq 'leaf' && $node_type2 eq 'leaf'){
            $check = 1;
        }
        elsif ($node_type eq 'internal' && $node_type2 eq 'internal'){
            $check = 1;
        }
        else {
            $check = 0;
            return 0;
            last;
        }
        pop @$ex1;
        pop @$ex2, isEqualShape(@$ex1, @$ex2);
    }
    return $check;
}

给我的结果是:当'strict refs'正在使用时,不能使用字符串('internal')作为ARRAY.我怎样才能解决这个问题？

Answer 1

要确定结构是否是相同的形状,您将需要使用递归算法(或具有堆栈的迭代算法).

您没有很多测试用例可以使用,但这应该可以解决问题:

sub isEqualShape {
    my ($x, $y) = @_;

    if (@$x == @$y and $$x[0] eq $$y[0]) {  # same length and node type
        for (2 .. $#$x) {
            isEqualShape($$x[$_], $$y[$_]) or return undef;  # same child shape
        }
        return 1;
    }
    return undef;
}