Haskellで逆ポーランド記法計算機を実装する
アルゴリズムの講義でスタックとキューを実装する機会があったのでまとめ．
まず，実行中に発生する可能性のある例外を捕捉するため，以下のクラスを作成した．記述には Eclipse を使用した．serialVersionUID とはなんなんだろう．よくわからないけど書けということなので書いた．
public class ListError extends Exception { private static final long serialVersionUID = 1L; public ListError( String message ){ super( message ); } }
スタック
スタックは値の挿入を行う pushdown，値の取得を行う get_top，値の削除を行う popup からなる．この辺は講義の内容に従っているため多少の違いはあるが内容を理解するだけであればこれでもいいと思う．
public class Stack { private final int MAX_STACK = 100; private int top; private int body[]; public Stack(){ top = 0; body = new int[MAX_STACK]; } public void pushdown( int value ) throws ListError { if( top < MAX_STACK - 1 ){ top = top + 1; body[top] = value; } else throw new ListError( "リストが満杯です (pushdown)" ); } public int get_top() throws ListError { if( top > 0 ) return body[top]; else throw new ListError( "リストは空です (get_top)" ); } public void popup() throws ListError { if( top > 0 ) top = top - 1; else throw new ListError( "リストは空です (popup)" ); } }
キュー
キューは値の挿入を行う enqueue，値を取得する get_f，値を削除する dequeue からなる．また使用している配列のサイズを超えてしまった場合，添字を 0 に戻すことで要素を上書きする．リングバッファとか言うらしい．これもスタックと同様に多少の違いはあるが気にしてはいけない．講義の内容に従うのだ．
public class Queue { private final int MAX_QUEUE = 100; private int head; private int tail; private int num; private int body[]; public Queue(){ head = 0; tail = 0; num = 0; body = new int[MAX_QUEUE]; } public void enqueue( int value ){ tail = tail + 1; if( tail >= MAX_QUEUE ) tail = 0; num = num + 1; body[tail] = value; } public int get_f() throws ListError { if( num > 0 ) if( head + 1 < MAX_QUEUE ) return body[head+1]; else return body[0]; else throw new ListError( "リストが空です (get_f)" ); } public void dequeue() throws ListError { if( num > 0 ){ head = head + 1; if( head >= MAX_QUEUE ) head = 0; num = num -1; } else throw new ListError( "リストが空です (dequeue)" ); } }
逆ポーランド記法
講義とは関係がないが，スタックとキューを使用し逆ポーランド記法計算機を作成した．入力された式の保持にキューを，式の評価にスタックを使用している．式の評価部分の実装は，リストの扱う向きを逆にすると左畳み込みが使用でき，より簡潔に記述することができる．というか参考にさせていただいた Haskell で逆ポーランド記法計算機を作る - Qiita がそうしている．ほぼここを見て書いたというのは口が裂けても言えない．参考にしたということで，丸写しでは面白くないので講義に合わせる形に変えて実装した．
type Stack = [Double] type Queue = [String] -- Stack functions pushdown :: Double -> Stack -> Stack pushdown x xs = xs ++ [x] get_top :: Stack -> Double get_top = last popup :: Stack -> Stack popup = init -- Queue functions enqueue :: String -> Queue -> Queue enqueue x xs = xs ++ [x] get_f :: Queue -> String get_f = head dequeue :: Queue -> Queue dequeue = tail -- Rpn functions rpnExec :: Stack -> String -> Stack rpnExec stack value = case value of "+" -> pushdown ( y + x ) ys "-" -> pushdown ( y - x ) ys "*" -> pushdown ( y * x ) ys "/" -> pushdown ( y / x ) ys _ -> pushdown ( read value :: Double ) stack where x = get_top stack xs = popup stack y = get_top xs ys = popup xs eval :: String -> String eval formula = show $ head $ foldl rpnExec [] $ words formula -- Main getFormula :: Queue -> IO () getFormula xs = do formula <- getLine if null formula then queue [eval x | x <- xs] else getFormula $ enqueue formula xs where queue [x] = putStrLn x queue xs = do queue [get_f xs] queue $ dequeue xs main :: IO () main = getFormula []
割と無理やり，というか突っ込みどころが満載な気がする．
