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入力文字列に一致する括弧のペアが少なくとも1つ含まれていない場合は、失敗することに注意してください。

最後に、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"

別のパターンマッチング条件で回避できます。

UPD：

より読みやすい解決策は、角かっこがバランスされている場合やその他の場合に必要な部分文字列を返す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 に答える