2

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

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

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

我试图通过计算开括号的数量直到第一个')'来创建一个 between 函数，但它不适用于像这样的字符串。

4

2 回答 2

7

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

例如：

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
于 2012-04-20T09:35:01.557 回答
3

使用辅助go函数的简单新手解决方案。

brackets :: String -> String
brackets string = go string 0 False
  where go (s:ss) 0 False | s /= '(' = go ss 0 False
        go ('(':ss) 0 False = '(' : go ss 1 True
        go (')':_) 1 True = ")"
        go (')':ss) n True = ')' : go ss (n-1) True
        go ('(':ss) n True = '(' : go ss (n+1) True
        go (s:ss) n flag = s : go ss n flag 
        go "" _ _ = ""

这个想法是为每个 记住一些左括号的计数器Char。当该计数器等于 1 并且Char等于)时 - 是时候返回所需的字符串了。

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

请注意，对于不平衡的字符串，此函数将返回带有未闭合括号的字符串，如下所示：

> brackets "a(a(a"
"(a(a"

可以通过另一个模式匹配条件来避免。

更新：

更具可读性的解决方案是如果括号平衡以及在其他情况下返回需要子字符串的balancedSubstring函数。:: String -> Maybe StringJustNothing

brackets :: String -> String
brackets string = go string 0 False
  where go (s:ss) 0 False | s /= '(' = go ss 0 False
        go ('(':ss) 0 False = '(' : go ss 1 True
        go (')':_) 1 True = ")"
        go (')':ss) n True = ')' : go ss (n-1) True
        go ('(':ss) n True = '(' : go ss (n+1) True
        go (s:ss) n flag = s : go ss n flag
        go "" _  _ = ""

isBalanced :: String -> Bool
isBalanced string = go string 0
  where go ('(':ss) n = go ss (n+1)
        go (')':ss) n | n > 0 = go ss (n-1)
        go (')':_ ) n | n < 1 = False
        go (_:ss) n = go ss n
        go "" 0 = True
        go "" _ = False

balancedSubstring :: String -> Maybe String
balancedSubstring string | isBalanced string = Just $ brackets string
balancedSubstring string | otherwise         = Nothing

所以现在balancedSubstring函数的结果更容易理解：

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

> balancedSubstring "a(a(a"
Nothing
于 2012-04-20T09:34:54.587 回答