木が "等しい"かどうかを確認する

Question

私はPerlを使用しています.2つの演算式ツリーが等しいかどうかを判断する必要があります。等しく、私は、木の形が等しいではなく、内に保持されている特定の値を意味します。たとえば、 '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; 
} 

私に与えられた結果は次のとおりです。「はrefs」の使用中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; 
}