calcRPN関数で電卓を作ろう
calcRPN
１。逆ポーランド式の解釈はどうやる？
このワークシートはMath by Codeの一部です。
(1*2)+(4-3)という中置式から木を作り、逆ポーランド記法ReversePolandNotation, RPNで出力すると、
1, 2, *, 4 ,3,- になることがわかった。
カンマが邪魔なので省くと、1 2 * 4 3 -だ。
では、逆ポーランド記法を通常の式に戻すことをやってみよう。
質問：演算子が後置の逆ポーランド記法RPN「4 3 2 ＋ 1 ー ＊」を普通の中置式にするとどうなるでしょうか。
4 3 2 + 1 - *
演算子だけとりだすと、+, - , *だ。
だから＋をして、ーをして、＊をしている。
では何と何に作用させているんだろう。
4 3 2＋ 1 ー ＊
まず、＋の直前の２数３と２を取り出して、(3+2)にして戻す。
4 (3＋2) 1 ー ＊
次は、ーの直前の２数(3+2)と1 を取り出して、(3＋2)ー1にして戻そう。
4 (3＋2) ー1＊
最後に＊の直前の２数4 と (3＋2) ー1 を取り出して、4 ＊( (3＋2) ー1 )にして戻そう。
だから、4 ＊ ( (3＋2) ー1 )となるね。
この手順は目で見ながら実行したのだけれど、空白を区切りとして、数値を演算子を読み取ることで
ルールから今の作業を実行したい。
質問：後置式を中置式に変換して返すプログラムはどうやればできるだろうか。
さて、さて、データ構造といえばスタックかキューかハッシュの出番かな？
左から順に、つまり入れた順に使うわけではないから、スタックでしょうか。
stackにSさんと名前をつけよう。
RPN＝「4 3 2＋ 1 ー ＊」を空白区切りでSさんにわたそう。
Sさんは数値ならどんどん上に積んでいく。
Sに左から4、3、2の順を渡すと、上か順にｘ、ｙ、残りをysと名付けるなら、x=２, y=３, ys=４となる。
もとの式の左右の順番とｘ，ｙの順番が逆になってしまうので計算順に注意しよう。
次は（＋）が出たから、上からx=２,y=３を取り出して、y+x=３+２=５をSさんに戻す。
残った４の上に５が積まれるので、上から順にx=5,y=4となる。
次の1はSさんに渡す。Sさんは上から順にx=1,y=5,ys=4となる。
次は（ー）が出たから、上からx=1,y=5を取り出して、y-x=5-1=4を戻す。
Sさんは上から順にx=4,y=4となる。
次も（＊）が出たから、上からx=4, y=4を取り出し、y*x=4*4=16を戻す。
x=16が入っている。
RPNが空になったとき、Sさんのスタックが１つの数値だけになりそれが答えになるね。
2。Haskellで電卓を作る。
複数の演算子があると理解しにくいので、まずは、１つだけで作ってみよう。
RPN=文字列を受取り、和を返す関数calcDiff( RPN)を作ってみよう。
文字列RPNをリストLに分解するwords関数を使う。
Lを左から順に読み取って処理は、左畳み込みfoldl関数にfoldStack関数にLと空のリストを渡す。
最後に畳み込んだあとのリストの先頭をhead関数で読み込む。
この３つの関数をパイプラインでつないだ、合成関数がcalcDiffです。
ただし、foldStack関数だけは未定義なので、where句で末尾にケース分けして反応を定義します。
foldStack関数が使うスタック（だたのリストです）Sは最初は空です。S＝[ ]
・Lからの読み取りが数値numなら, Sの中身xsの先頭にnumを追加する。Sの先頭から順にx,y,ysとなる。
・Lからの読み取りが”-”なら,Sの先頭からx,yなので、y-xを計算してSの先頭に追加する。
最後にSの先頭(head)を読み取る。
これをHaskellでかくとこうなります。
calcDiff = head . foldl foldStack [] . words
where
foldStack (x:y:ys) "-" =(y-x):ys
foldStack xs num = read num :xs
これを使うには、
コマンドラインでカレントディレクトリをプログラムファイルのある場所に移動し、
ghciと打ちHaskellを立ち上げてから、プログラムファイルをロード（:l ファイル名）します。
ghci>calcDiff " 10 - 2 "
8
ghci>calcDiff " 2 - 10 "
-8
となるので、x,y の逆順で(y-x)を計算して残りysに積んでいるのが効いてますね。
質問：RPN文字列を読み取り、たし算以外の四則計算などもできる関数calcRPNはどうやれば作れますか。
簡単です。読み取った演算記号が-以外の場合の式をwhere句に、好きなだけ追加するだけです。
たとえば、sum や ln など、haskellが読める関数がそのままかけます。
calcRPN = head . foldl foldStack [] . words
where
foldStack (x:y:ys) "+" =(y+x):ys
foldStack (x:y:ys) "-" =(y-x):ys
foldStack (x:y:ys) "*" =(y*x):ys
foldStack (x:y:ys) "/" =(y/x):ys
foldStack (x:y:ys) "^" =(y**x):ys
foldStack (x:xs) "ln" = log x:xs
foldStack xs "sum" =[sum xs]
foldStack xs num = read num :xs
ghci>calcRPN "4 3 2 + 1 - *"
16
ghci>calcRPN "2 10 ^"
1024.0
ghci>calcRPN "2.71828 ln"
0.999999327347282
ghci>calcRPN "10 20 20 sum"
60.0
やはり、haskellのような言語は、関数を組み合わせる、加工型、関数型プログラムには向いてますね。
すばらしい。
３．juliaで電卓を作る。
質問：関数名を同じにしてjuliaでも電卓を作るにはどうしたらよいでしょうか。
juliaにもfoldl,foldr関数があるのですが、簡単な演算のくり返しでは作動しますが、
一般の関数は難しいようです。
しかたないので、whileで代用しましょう。
words関数とfoldStack関数を作っておき、単体で作動テストをしてから、
それらを組み込んだcalcRPN関数を作ります。
function words(x) # 1スペースで区切る
return split(x," ")
end
function foldStack(lst)
ope = ["*","+","-","/"]
opeS = Set(ope)
Stack =[]
item = popfirst!(lst)
# y x ope を抜き出して Stack の上からx ,y の順につまれた数で
# z= y ope x を計算します。
while item ∉ opeS
pushfirst!(Stack,item)
item = popfirst!(lst)
end
if item in ope
x = parse.(Int,popfirst!(Stack))
y = parse.(Int,popfirst!(Stack))
z = 0
if item == ope[1]
z = y * x
elseif item == ope[2]
z = y + x
elseif item == ope[3]
z = y - x
elseif item == ope[4]
z = y / x
end
end
#取り出した３要素y,x,opeを１要素zにしてリストlstに戻し、
#計算しなかったStackの残りも、リストlstにもどします。
pushfirst!(Stack,z)
while length(Stack)>0
p = string(popfirst!(Stack))
pushfirst!(lst,p)
end
return lst
end
function calcRPN(RPN)
res = RPN |> words
while length(res)>2
res = foldStack(res)
end
return parse.(Int,res)
end
"4 3 2 + 1 - *" |> calcRPN
#==========================
[OUT]
1-element Vector{Int64}:
16
RPNの数式ならば加減乗除が自由にできます。
二項演算の種類を増やしたり、単項演算,多項演算もできるようにすることも可能ですが、
あちこち行数が増えてしまいます。
まあ、juliaは演算「//」ですぐに分数計算に切り替わるので、分数電卓を作りたかったら向いているかもしれません。
質問：このcalcRPN関数のもとになったfoldStack関数を改造して、もっと計算できる演算の種類をふやしてみましょう。
また、geogebraでcalcRPN電卓を作るにはどうしたらよいでしょうか。
geogebraで作るにはRPN式をスペースで区切りリストlstにします。
演算個数opedを読み取ります。使われている演算記号リストopeinを作ります。
最初の演算記号の位置を読み取ったら、opePos1に格納します。
opePos1までの３要素をrpn1というリストにします。
rpn1を中置順に直して、textToNumberで計算して、
もとのリストから３個削除して、計算結果v1を挿入します。
すると、lstからopein(1)だけを計算したリストlst1が作られます。
もし、演算個数opedが１より大きかったら、同様にしてlst1のrpn2を計算結果v2に置き換えたlst2を
作ります。opedが１より大きくなかったら、v2はv1のままでlst2はlst1のままにします。
もし、演算個数opedが２より大きかったら、同様にしてrpn3を計算して、結果answを得ます。大きくなかったら、answはv2のままです。