スタックと文字列変換

初期状態が空であるスタックを用いて数字列を置換することを考える．スタックに対して，二つの操作「入力側の数字列の先頭の一つの数字をスタックに入れる」と「スタックから一つの数字を取り出して印字する」があり，それぞれの操作をS とXで表す．S とX を並べた列を操作列という．例えば，入力数字列1234 に対して，SSXSSXXX という操作列の操作を左から右に順に作用させると，数字列1234 は2431 に置換されて印字される．

(i)操作列O1O2 . . .Om (Oi ∈ {S,X}) を数字列12 . . .n (n ≥ m) に作用させて出力される数字列を求める問題

(ii) 数字列12 . . . n をp1p2 . . .pn に置換する操作列を生成する問題

Haskellで実装してみた。

import Data.Maybe

stackTrans' :: [Char] ->[Int]->Int-> String
stackTrans' [] xs n = []
stackTrans' ('S':ss) xs n = stackTrans' ss (n:xs) $n+1
stackTrans' ('X':ss) (x:xs) n = show x ++ stackTrans' ss xs n
stackTrans :: String -> String
stackTrans s = stackTrans' s [] 1

numTrans::[Int]-> Maybe String
numTrans ps = foldr1 madd mc
  where mc = numTrans' ps [] 1
        
madd (Just s)(Just t) = Just $ s++t
madd  _ Nothing = Nothing

numTrans'::[Int]->[Int]->Int->[Maybe String]
numTrans' [] xs n = []
numTrans' ps [] n = (:) (Just "S") $ numTrans' ps [n] $n+1
numTrans' (p:ps) (x:xs) n
  | p == x  =(:) (Just "X") $ numTrans' ps xs n
  | p >= n  =(:) (Just "S") $ numTrans' (p:ps) (n❌xs) $n+1
  | p <  n  = Nothing:[]

実行例。

*Main> stackTrans "SSSSSXXSXSXXXX"
"5467321"
*Main> numTrans [5,4,6,7,3,2,1]
Just "SSSSSXXSXSXXXX"

コンテンツ