確定樹是否「相等」

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

確定樹是否「相等」

回答

相關問題