スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 逆ポーランド記法

この記事は、F# Advent Calendar jp: 2010 への参加記事です。 
 
逆ポーランド記法で書かれた、文字列を計算するプログラムを書いてみました。(手抜きですが。) 
(逆ポーランド記法についてはこちら
まず、整数と二項演算子を表す型を定義しておきます。 
 
> type Token = 
    | Num of int 
    | Op  of (int -> int-> int);; 
 
type Token = 
  | Num of int 
  | Op of (int -> int -> int) 
 
使用する二項演算子をマップにしておきます。 
 
> let opMap = Map.ofList [("+",(+));("-",(-));("*",(*));("/",(/))];;  
 
val opMap : Map<string,(int -> int -> int)> = 
  map 
    [("*", <fun:opMap@16-2>); ("+", <fun:opMap@16>); ("-", <fun:opMap@16-1>); 
     ("/", <fun:opMap@16-3>)] 
 
文字列をToken型のリストに直す関数を定義します。(手抜きなので、数字や演算子の間は正確に半角スペース1個、先頭と末尾には半角スペースなしという条件が付きます。) 
 
> let convStrToTokenLst (str:string) = 
    str.Split([|' '|]) 
    |> List.ofArray 
    |> List.map(fun s ->    let findOpResult = opMap.TryFind s 
                            if findOpResult.IsSome then  
                                Op(findOpResult.Value) 
                            else 
                                let (isNum,v) = System.Int32.TryParse s    
                                if isNum = true then  
                                    Num(v) 
                                else 
                                    failwith "計算式の書式が不正です");; 
 
val convStrToTokenLst : string -> Token list 
 
ちょっと使用してみます。 
 
> convStrToTokenLst "2 1 - 10 *";; 
val it : Token list = 
  [Num 2; Num 1; Op <fun:opMap@16-1>; Num 10; Op <fun:opMap@16-2>] 
 
ではこれを読み込みながらスタックの状態を変化させる関数を定義します。 
 
> //remTokenLstは未処理のトークンリスト、stackLstはスタック代わりに用いるリスト 
let rec processToken remTokenLst stackLst  = 
    match remTokenLst,stackLst with 
    //最後の段階ではスタックに残った一つの値が答え 
    | []              ,v::[]        -> v 
    //トークンが数字の場合はスタックに数字を押し込む 
    | Num(n)::rem,sl           -> processToken rem (n::sl)  
    //トークンが演算子の場合はスタックから数字を二つ取り出し、演算結果をスタックに押し込む 
    | Op(op)::rem,v1::v2::tail -> processToken rem ((op v2 v1)::tail)    
    | _ -> failwith "error";; 
 
val processToken : Token list -> int list -> int 
 
では二つを組み合わせて、逆ポーランド記法で書かれた文字列を計算(評価)する関数eValReversePolishNotationを定義します。 
 
> let eValReversePolishNotation expression = 
      processToken (convStrToTokenLst expression) [];; 
 
val eValReversePolishNotation : string -> int 
 
では使ってみます。 
 
> eValReversePolishNotation "2 1 - 10 *";; 
val it : int = 10 
 
mapにさらに2項演算子を登録することで拡張可能です。 
 
let opMap = Map.ofList [("+",(+));("-",(-));("*",(*));("/",(/));("max",max)];;  
としておけば、 
 
> eValReversePolishNotation "2 1 max 10 *";; 
val it : int = 20 
 
全コードは以下の通りです。 
 
type Token = 
    | Num of int 
    | Op  of (int -> int-> int) 
 
let opMap = Map.ofList [("+",(+));("-",(-));("*",(*));("/",(/));("max",max)];;  
 
let convStrToTokenLst (str:string) = 
    str.Split([|' '|]) 
    |> List.ofArray 
    |> List.map(fun s ->    let findOpResult = opMap.TryFind s 
                            if findOpResult.IsSome then  
                                Op(findOpResult.Value) 
                            else 
                                let (isNum,v) = System.Int32.TryParse s    
                                if isNum = true then  
                                    Num(v) 
                                else 
                                    failwith "計算式の書式が不正です") 
     
//remTokenLstは未処理のトークンリスト、stackLstはスタック代わりに用いるリスト 
let rec processToken remTokenLst stackLst  = 
    match remTokenLst,stackLst with 
    //最後の段階ではスタックに残った一つの値が答え 
    | []          ,v::[]        -> v 
    //トークンが数字の場合はスタックに数字を押し込む 
    | Num(n)::rem,sl           -> processToken rem (n::sl)  
    //トークンが演算子の場合はスタックから数字を二つ取り出し、演算結果をスタックに押し込む 
    | Op(op)::rem,v1::v2::tail -> processToken rem ((op v2 v1)::tail)    
    | _ -> failwith "error" 
 
let eValReversePolishNotation expression = 
      processToken (convStrToTokenLst expression) [] 
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

trackback


この記事にトラックバックする(FC2ブログユーザー)

フォースモドキVer.0

【F#】フォースモドキVer.0

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。