识别树是否“相等”

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 之间进行比较时，这会返回“形状不等于”，正如预期的那样。但是，在比较 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;
}

给我的结果是：在使用“严格引用”时不能使用字符串（“内部”）作为数组。 我该如何解决这个问题？

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