読者です 読者をやめる 読者になる 読者になる

Calmery.me

みっかぼうずにならないようがんばる

Haskellで逆ポーランド記法計算機を実装する

Java Haskell Algorithm

アルゴリズムの講義でスタックとキューを実装する機会があったのでまとめ.

まず,実行中に発生する可能性のある例外を捕捉するため,以下のクラスを作成した.記述には 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 []

割と無理やり,というか突っ込みどころが満載な気がする.