Определение совпадающих скобок в Haskell

Вы можете использовать функцию, которая просто проходит по строке, отслеживая стек индексов открывающих скобок. Всякий раз, когда вы сталкиваетесь с закрывающей скобкой, вы знаете, что она соответствует индексу на вершине стека.

Например:

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*)"]

Следуя предложению Фрериха Раабе, теперь мы также можем написать функцию, которая возвращает только крайний левый сегмент:

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

Простое решение для новичков с использованием вспомогательной функции 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