确定树是否“相等”

我正在使用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; 
}

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

来源

2011-02-11 Sheldon

你从来没有真正修改`$ node_type`或`$ node_type2`。 – 2011-02-11 01:16:42

是的，我注意到，所以我试着从数组中弹出数值，但最终导致引用错误。我会编辑我的问题，并显示我已经尝试了什么以及结果发生了什么。 – Sheldon 2011-02-11 01:18:33

要确定结构是否具有相同的形状，您将需要使用递归算法（或带有堆栈的迭代算法）。

你没有太多的测试用例的工作，但是这应该做的伎俩：

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

来源

2011-02-11 01:17:50

确定树是否“相等”

回答

相关问题