8

ツリー構造のReadを実装するのに苦労しています。ABC(DE)F左連想文字列 (括弧付き) を取り、それをツリーに変換したいと考えています。その特定の例はツリーに対応します

木.

私が使用しているデータ型は次のとおりです（ただし、提案は受け付けています）。

data Tree = Branch Tree Tree | Leaf Char deriving (Eq)

その特定のツリーは、Haskell では次のようになります。

example = Branch (Branch (Branch (Branch (Leaf 'A')
                                         (Leaf 'B'))
                                 (Leaf 'C'))
                         (Branch (Leaf 'D')
                                 (Leaf 'E')))
                 (Leaf 'F')

私のshow関数は次のようになります。

instance Show Tree where
    show (Branch l r@(Branch _ _)) = show l ++ "(" ++ show r ++ ")"
    show (Branch l r) = show l ++ show r
    show (Leaf x) = [x]

readそのような関数を作りたい

read "ABC(DE)F" == example
4

3 に答える 3

13

これは、解析ライブラリを使用すると、コードが驚くほど短くなり、非常に表現力豊かになる状況です。（これに答えるために実験していたとき、それがとてもきちんとしていたことに驚きました！）

私はParsecを使用し (この記事には詳細情報へのリンクがいくつかあります)、それを (モナドではなく) 「アプリケーション モード」で使用します。

コード

まず、さまざまなインポートと定義:

import Text.Parsec

import Control.Applicative ((<*), (<$>))

data Tree = Branch Tree Tree | Leaf Char deriving (Eq, Show)

paren, tree, unit :: Parsec String st Tree

現在、ツリーの基本単位は、単一の文字 (かっこではない) またはかっこで囲まれたツリーのいずれかです。(括弧で囲まれたツリーは、との間の通常のツリー)です。通常のツリーは、左に関連付けられたブランチに配置されたユニットにすぎません (非常に自己再帰的です)。Haskell と Parsec の場合:

-- parenthesised tree or `Leaf <character>`
unit = paren <|> (Leaf <$> noneOf "()") <?> "group or literal"

-- normal tree between ( and )
paren = between (char '(') (char ')') tree  

-- all the units connected up left-associatedly
tree = foldl1 Branch <$> many1 unit

-- attempt to parse the whole input (don't short-circuit on the first error)
onlyTree = tree <* eof

(はい、それがパーサー全体です!)

paren必要に応じて、なくても構いませんunitが、上記のコードは非常に表現力豊かなので、そのままにしておくことができます。

簡単な説明として（ドキュメントへのリンクを提供しました）：

  • (<|>)基本的に「左パーサーまたは右パーサー」を意味します。
  • (<?>)より適切なエラー メッセージを作成できます。
  • noneOf指定された文字リストにないものはすべて解析します。
  • between3 つのパーサーを取り、1 番目と 2 番目のパーサーで区切られている限り、3 番目のパーサーの値を返します。
  • charその引数を文字どおりに解析します。
  • many1その引数の 1 つ以上を解析してリストに入れます (ゼロ以上を解析するmany1のではなく、空の文字列は無効であるように見えます)。many
  • eof入力の末尾に一致します。

関数を使用しparseてパーサーを実行できます (これは を返しますEither ParseError Tree。これLeftはエラーでRightあり、正しい解析です)。

としてread

これを like 関数として使用すると、次のreadようになります。

read' str = case parse onlyTree "" str of
   Right tr -> tr
   Left er -> error (show er)

(以前はread'との競合を避けてきましPrelude.readた。Readインスタンスが必要な場合は、実装するためにもう少し作業を行う必要がありますreadPrec(または必要なものは何でも) が、実際の解析が既に完了しているため、それほど難しくはありません。)

例

いくつかの基本的な例:

*Tree> read' "A"
Leaf 'A'

*Tree> read' "AB"
Branch (Leaf 'A') (Leaf 'B')

*Tree> read' "ABC"
Branch (Branch (Leaf 'A') (Leaf 'B')) (Leaf 'C')

*Tree> read' "A(BC)"
Branch (Leaf 'A') (Branch (Leaf 'B') (Leaf 'C'))

*Tree> read' "ABC(DE)F" == example
True

*Tree> read' "ABC(DEF)" == example
False

*Tree> read' "ABCDEF" == example
False

エラーのデモンストレーション:

*Tree> read' ""
***Exception: (line 1, column 1):
unexpected end of input
expecting group or literal

*Tree> read' "A(B"
***Exception: (line 1, column 4):
unexpected end of input
expecting group or literal or ")"

tree最後に、との違いonlyTree:

*Tree> parse tree "" "AB)CD"     -- success: ignores ")CD"
Right (Branch (Leaf 'A') (Leaf 'B'))

*Tree> parse onlyTree "" "AB)CD" -- fail: can't parse the ")"
Left (line 1, column 3):
unexpected ')'
expecting group or literal or end of input

結論

パーセクすごい！この答えは長くなるかもしれませんが、その核心はすべての作業を行うわずか 5 ～ 6 行のコードです。

于 2012-05-02T08:28:25.190 に答える
6

これはスタック構造のように見えます。入力 string に遭遇すると、"ABC(DE)F"見つけLeafた任意のアトム (括弧なし) をアキュムレータ リストに入れます。リストに 2 つの項目がある場合は、Branchそれらをまとめます。これは次のようなもので行うことができます (メモ、テストされていません。アイデアを提供するためだけに含まれています):

read' [r,l] str  = read' [Branch l r] str
read' acc (c:cs) 
   -- read the inner parenthesis
   | c == '('  = let (result, rest) = read' [] cs 
                 in read' (result : acc) rest
   -- close parenthesis, return result, should be singleton
   | c == ')'  = (acc, cs) 
   -- otherwise, add a leaf
   | otherwise = read' (Leaf c : acc) cs
read' [result] [] = (result, [])
read' _ _  = error "invalid input"

これには多少の変更が必要になる場合がありますが、正しい軌道に乗るには十分だと思います。

于 2012-05-02T05:48:30.570 に答える
3

dbaupp による parsec の回答は非常に理解しやすいものです。「低レベル」のアプローチの例として、成功の継続を使用して左連想ツリーの構築を処理する手書きのパーサーを次に示します。

instance Read Tree where readsPrec _prec s = maybeToList (readTree s)

type TreeCont = (Tree,String) -> Maybe (Tree,String)

readTree :: String -> Maybe (Tree,String)
readTree = read'top Just where
  valid ')' = False
  valid '(' = False
  valid _ = True

  read'top :: TreeCont -> String -> Maybe (Tree,String)
  read'top acc s@(x:ys) | valid x =
    case ys of
      [] -> acc (Leaf x,[])
      (y:zs) -> read'branch acc s
  read'top _ _ = Nothing

  -- The next three are mutually recursive

  read'branch :: TreeCont -> String -> Maybe (Tree,String)
  read'branch acc (x:y:zs) | valid x = read'right (combine (Leaf x) >=> acc) y zs
  read'branch _ _ = Nothing

  read'right :: TreeCont -> Char -> String -> Maybe (Tree,String)
  read'right acc y ys | valid y = acc (Leaf y,ys)
  read'right acc '(' ys = read'branch (drop'close >=> acc) ys
     where drop'close (b,')':zs) = Just (b,zs)
           drop'close _ = Nothing
  read'right _ _ _ = Nothing  -- assert y==')' here

  combine :: Tree -> TreeCont
  combine build (t, []) = Just (Branch build t,"")
  combine build (t, ys@(')':_)) = Just (Branch build t,ys)  -- stop when lookahead shows ')'
  combine build (t, y:zs) = read'right (combine (Branch build t)) y zs
于 2012-05-02T13:34:07.810 に答える