获得匹配括号的索引

Question

你好，我正在尝试打印下列括号模式的索引：

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

如下所示：

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

我有办法做到这一点吗？

Answer 1

推到左边括号上的堆栈，右边弹出。

#!/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;

Answer 2

有趣的问题！接受的答案很好，但这里有另一种方法，因为看到另一种解决方案总是有教育意义的。

#!/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);

输出与您想要的输出完全相同。死在不匹配的括号上(choroba的代码也可以在elsif块中进行适当的测试)。不匹配的括号导致没有第二个数字的行，并且它们也将在@match中在while循环之后残留。

我选择了使用Perl的模式匹配，而不是将字符串分解成单独的字符，并对所有字符进行迭代。相反，我使用"g“修饰符依次对每个开括号或结束括号进行匹配。因此，循环只对感兴趣的字符进行迭代。pos()函数在$string上返回上一次匹配后的点，因此我需要减去1才能得到基于零的输出。

另一个关键的区别是，我在@out中积累，并通过注意@out的最后一个索引来跟踪相应的闭包，并将其推到@match上。然后，当我找到结束括号时，我会弹出@match，并在该位置将第二个元素添加到@out中的子数组中。这消除了对最终结果进行排序的需要，因为@out已经按照打开括号的顺序排列。