确定匹配括号在Haskell

Question

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

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

如何确定对于第一个所述匹配支架？ （意思是(def(gh)il(mn(01))afg)）

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

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被发现。

以下功能为您提供了一个字符串的所有正确parenthesised段：

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拉贝的建议，我们现在也可以编写一个函数，只返回最左边的部分：

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 

Answer 2

简单的新手解决方案使用帮手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" 

它可以与其他模式匹配条件是可以避免的。

---

UPD：

更可读的解决方案是balancedSubstring函数:: String -> Maybe String返回Just要求子串如果括号是在其它情况下平衡和Nothing。

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