5

バランスブラケットの問題を解決しようとしています。私は継続的な IO を実行したくありません。むしろ、getLine を 1 回呼び出して、結果の文字列を解析したいと考えています。したがって、問題を解決する関数は、入力文字列の未使用部分とブラケット スタックの 2 つの異なる状態を処理します。

スタックを操作するためのいくつかの関数をセットアップしたい:

type Stack = String

pop :: Stack -> (Char,Stack)
pop (x:xs) = (x,xs)

push :: Char -> Stack -> ((),Stack)
push a xs = ((),a:xs)

State モナドで操作している場合はそれで問題ありませんが、StateT モナドで操作しています。

balanced :: StateT Stack (State String) Bool

スタックに重複したモナドを持たないように言われたことは知っています。プッシュとポップの定義を単純化する方法が好きなので、私はこのようにしています。

2 つの問題:

  1. 何をしても、StateT に含まれるスタックにプッシュとポップを適用する方法が見つかりません。
  2. メイン関数からこれを呼び出す方法がわかりません

残りのコードは次のとおりです

next :: String -> (Maybe Char,String)
next ""     = (Nothing,[])
next (x:xs) = (Just x,xs)

balanced = do
            c <- lift (state next)
            case c of
              Nothing -> return True
              Just c  -> if elem c open 
                         then (push c) >> balanced
                         else if elem c close 
                              then pop >>= \x ->
                                if eq x c
                                then balanced
                                else return False
                              else balanced
          where open  = "<{(["
                close = "])}>"
                eq '(' ')' = True
                eq '{' '}' = True
                eq '<' '>' = True
                eq '[' ']' = True
                eq  _   _  = False
4

1 に答える 1

7

あなたの問題は、pushandpopが、モナドのdoブロックで使用しようとしている通常の非モナド関数であることです。next関数を使用して呼び出しているため、正しく使用してstateいますが、おそらくお気づきのようstateに、プレーンStateモナドに対してのみ機能し、 では機能しませんStateT。

state次のようなモナド変換バージョンを実装できます。

stateT :: Monad m => (s -> (a, s)) -> StateT s m a
stateT f = do
    (x, s') <- gets f
    put s'
    return x

そして、 と を使用してbalanced関数で使用pushしpopます。

balanced :: StateT Stack (State String) Bool
balanced = do
            c <- lift (state next)
            case c of
              Nothing -> return True
              Just c  -> if elem c open
                         then (stateT $ push c) >> balanced
                         else if elem c close
                              then stateT pop >>= \x ->
                                if eq x c
                                    then balanced
                                    else return False
                              else balanced
          where open  = "<{(["
                close = "])}>"
                eq '(' ')' = True
                eq '{' '}' = True
                eq '<' '>' = True
                eq '[' ']' = True
                eq  _   _  = False

関数は次のように呼び出されます。

evalState (evalStateT balanced []) s

sは初期文字列、は初期スタック[]です。

于 2012-02-08T06:41:00.693 に答える