一种Parentheses匹配算法

Question

您将得到一个字符串s。保证字符串相等，并且至少有一个[s和]s，并且保证括号是平衡的。该字符串还可以有其他字符。

目标是输出/返回一个元组列表或包含每个[和]对索引的列表。

注意:字符串是零索引的.

示例：!^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][]应该返回

[(8, 41), (20, 33), (21, 27), (36, 39), (42, 48), (49, 50)]或类似于此的东西。元组是不必要的。也可以使用列表。

测试用例：

input:[[asdf][][td([)ty54g% ]hg[[f]u][f[[jhg][gfd]sdf]sdfs]ghd]fr43f]
output:[(0, 62),(1, 6), (7, 8), (9, 56), (13, 22), (25, 30), (26, 28), (31, 52), (33, 47), (34, 38), (39, 43)]
input:[[][][][]][[][][][[[[(]]]]]))
output:[(0, 9), (1, 2), (3, 4), (5, 6), (7, 8), (10,26),(11, 12), (13, 14), (15, 16), (17, 25), (18, 24), (19, 23), (20, 22)]
input:[][][[]]
output:[(0, 1), (2, 3), (4, 7), (5, 6)]
input:[[[[[asd]as]sd]df]fgf][][]
output:[(0, 21), (1, 17), (2, 14), (3, 11), (4, 8), (22, 23), (24, 25)]
input:[]
output:[(0,1)]
input:[[(])]
output:[(0, 5), (1, 3)]

这是密码-高尔夫，所以每种编程语言的最短代码(以字节为单位)获胜。

Answer 1

脑-Flak经典，108个字节

{((((((([][][]){}){}){}()){}){}{}[])()()){{}<>{}(<>)}{}((){[](<{}>)}{}){{}<>[({}<[{}]>)](<>)}{}<>(({}()))<>}

在网上试试！

将每个打开的[存储在正确的堆栈中，并在我们到达]时输出。

Answer 2

Python 2，74字节

s=[];i=0
for c in input():
 if'['==c:s+=i,
 if']'==c:print s.pop(),i
 i+=1

在网上试试！

Answer 3

Java 10，95字节

将输入字符串作为Unicode代码点的int[]的void。

s->{int r=0,w=0;for(var c:s){if(c==91)s[w++]=r;if(c==93)System.out.println(s[--w]+","+r);r++;}}

在网上试试

Ungolfed

s -> {
    int r = 0, w = 0;
    for (var c : s) {
        if (c == 91)
            s[w++] = r;
        if (c == 93)
            System.out.println(s[--w] + "," + r);
        r++;
    }
}

Acknowledgments

• 感谢Jonathan将输入字符串用作堆栈的想法(这里)