Получение индексов совпадающих скобок - PullRequest
Новая
       8

Получение индексов совпадающих скобок

3 голосов
/ 21 мая 2019

Привет, я пытаюсь напечатать индексы следующего шаблона скобок: 

((((((...)))(((...))))))

следующим образом: 

0 23
1 22
2 21
3 11
4 10
5 9
12 20
13 19
14 18

Я пытался добиться этого с помощью этого кода на Perl, как указано ниже: 

#!/usr/bin/perl
use strict;
use warnings;

my $string = '((((((...)))(((...))))))';
my @myarray = split('', $string); 
my @stack;
my @stack1;



while (my ($index, $element) = each(@myarray))
{

   if ($element eq '(')
   {
   push(@stack, $index);  
   }

   if ($element eq ')')
   {
   push(@stack1, $index);  
   }  
}


print "$stack[$_]-$stack1[$_]\n" for (0 .. $#stack);

Но приведенный выше код дает мне следующий вывод, который не является обязательным: 

0-9
1-10
2-11
3-18
4-19
5-20
12-21
13-22
14-23

Есть ли способ, которым я могу этого достичь?

Ответы [ 2 ]

6 голосов
/ 21 мая 2019

Нажмите на стопку в скобках слева, всплывет справа. 

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my $string = '((((((...)))(((...))))))';

my @output;
my @stack;

my $pos = 0;
for my $char (split //, $string) {
    if ($char eq '(') {
        push @stack, $pos;
    } elsif ($char eq ')') {
        push @output, [ pop @stack, $pos ];
    }
    ++$pos;
}
say "@$_" for sort { $a->[0] <=> $b->[0] } @output;
2 голосов
/ 21 мая 2019

Веселый вопрос! Принятый ответ хорошо, но вот другой способ сделать это, потому что всегда полезно увидеть другое решение. 

#!/usr/bin/perl

use strict;
use warnings;

my $string = '((((((...)))(((...))))))';

my (@out, @match);

while ($string =~ m/([()])/g) {
    my $p = pos($string) - 1;
    if ($1 eq '(') {
        push @out, [$p];
        push @match, $#out;
    }
    else {
        die "mismatched paren at char $p\n"
            unless @match;
        $out[pop @match][1] = $p;
    }
}

for (@out) { print "@$_\n" }

exit(0);

Выход в точности соответствует желаемому результату. Умирает от несоответствующих скобок (что может сделать код Чоробы с соответствующим тестом в блоке elsif). Несоответствующие круглые скобки приводят к строкам без второго числа, и они также будут остаточными в @match после цикла while.

Я решил немного использовать сопоставление с шаблоном Perl вместо того, чтобы разбивать строку на отдельные символы и перебирать их все. Вместо этого я сопоставляю каждую открывающую или закрывающую скобку по очереди, используя модификатор «g». Таким образом, цикл повторяется только по интересующим символам. Функция pos() в $string возвращает точку после последнего совпадения, поэтому мне нужно вычесть единицу, чтобы получить вывод на основе нуля.

Другое ключевое отличие состоит в том, что я накапливаюсь в @out и отслеживаю соответствующее закрытие, отмечая последний индекс @out, нажимая на @match. Затем я выскакиваю @match, когда нахожу закрывающие скобки, и добавляю второй элемент в подмассив в @out в этой позиции. Это устраняет необходимость сортировки окончательного результата, поскольку @out уже находится в порядке открывающих скобок.

...