haskell - 确定 Haskell 中的匹配括号

Question

假设我有一个字符串，例如:

abc(def(gh)il(mn(01))afg)lmno(sdfg*)

如何确定第一个匹配的括号？ (意思是(def(gh)il(mn(01))afg))

我尝试通过计算第一个“)”之前的开括号数量来创建一个 Between 函数，但它不适用于像这样的字符串。

Answer 1

您可以使用一个函数来简单地遍历字符串，同时跟踪左括号的索引堆栈。每当遇到右括号时，您就知道它与堆栈顶部的索引匹配。

例如:

parenPairs :: String -> [(Int, Int)]
parenPairs = go 0 []
  where
    go _ _        []         = []
    go j acc      ('(' : cs) =          go (j + 1) (j : acc) cs
    go j []       (')' : cs) =          go (j + 1) []        cs -- unbalanced parentheses!
    go j (i : is) (')' : cs) = (i, j) : go (j + 1) is        cs
    go j acc      (c   : cs) =          go (j + 1) acc       cs

此函数返回属于匹配括号对的所有索引对的列表。

将该函数应用于示例字符串会得到:

> parenPairs "abc(def(gh)il(mn(01))afg)lmno(sdfg*)"
[(7,10),(16,19),(13,20),(3,24),(29,35)]

您感兴趣的左括号出现在索引 3 处。返回的列表显示匹配的右括号可在索引 24 处找到。

以下函数为您提供字符串的所有正确括号部分:

parenSegs :: String -> [String]
parenSegs s = map (f s) (parenPairs s)
  where
    f s (i, j) = take (j - i + 1) (drop i s)

例如:

> parenSegs "abc(def(gh)il(mn(01))afg)lmno(sdfg*)"
["(gh)","(01)","(mn(01))","(def(gh)il(mn(01))afg)","(sdfg*)"]

根据 Frerich Raabe 的建议，我们现在还可以编写一个仅返回最左边段的函数:

firstParenSeg :: String -> String
firstParenSeg s = f s (minimum (parenPairs s))
  where
    f s (i, j) = take (j - i + 1) (drop i s)

例如:

> firstParenSeg "abc(def(gh)il(mn(01))afg)lmno(sdfg*)"
"(def(gh)il(mn(01))afg)"

请注意，如果输入字符串不包含至少一对匹配的括号，firstParenSeg 将失败。

最后，对 parenPairs 函数进行了一个小修改，使其在不平衡的括号上失败:

parenPairs' :: String -> [(Int, Int)]
parenPairs' = go 0 []
  where
    go _ []        []         = []
    go _ (_ : _ )  []         = error "unbalanced parentheses!"
    go j acc       ('(' : cs) =          go (j + 1) (j : acc) cs
    go j []        (')' : cs) = error "unbalanced parentheses!"
    go j (i : is)  (')' : cs) = (i, j) : go (j + 1) is        cs
    go j acc       (c   : cs) =          go (j + 1) acc       cs