Определение того, равны ли деревья - PullRequest
Новая
       12

Определение того, равны ли деревья

1 голос
/ 11 февраля 2011

Я использую Perl, и мне нужно определить, равны ли два дерева арифметических выражений. Под равным я имею в виду форму деревьев, а не конкретные значения, содержащиеся внутри. Так, например, ['internal', '-' ['leaf', 5] ['leaf', 4]] не совпадает с ['internal', 'medium', ['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;
}

Результат, который мне дали: не может использовать строку ('internal') в качестве ARRAY, когда используются 'строгие ссылки'. Как я могу это исправить?

1 Ответ

6 голосов
/ 11 февраля 2011

Чтобы определить, имеют ли структуры одинаковую форму, вам нужно использовать рекурсивный алгоритм (или итеративный со стеком).

У вас не так много тестовых случаев для работы, но это должно сработать: 

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