나무가 "같음"인지 확인

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