11

23

[Ruby] rubyで2+3*4 を計算してみた (電卓プログラム/中置記法/後置記法/逆ポーランド記法/字句解析/構文解析)

2011.11.23(14:20)

字句解析と構文解析の実験用にごく普通の数式を計算するプログラムを作ってみた。目的がそれなのでevalとか数値オブジェクトにオペレータをsendするようなことはしない。


(1) "2+3*4" のような表記方法は中置記法(infix notation)と
呼ばれる。まずこの文字列を数値と演算子に分解する。
先の文字列を、["2","+","3","*","4"] に分解する。

(2) これをコンピュータで計算しやすいように、
後置記法(postfix notation)に変換する。
後置記法は逆ポーランド記法(reverse polish notation)とも呼ばれる。
前の例は、["2","3","4","*","+"] に変換する。
これは左から、2に(3に4を掛けもの)を足す、と読む。
こう変換しておけば、コンピュータは前から順番に処理すれば
計算できるのでラクなのである。

(3) 後置記法に変換したものを、前から順番に計算して値を求める。

この手順にしたがって、rubyでプログラムしてみる。




(1) 数式文字列を、数値と演算子に分解する。
基本的には前から順番に見ていって、数値と演算子を分ければいいのだが、
単項演算子のマイナスと二項演算子のマイナスが同じ"-"であるので
それを区別するためにちょっと工夫が必要。

"2-3"のマイナスは二項演算子、"-3*2"のマイナスは単項演算子である。
前者は["2","-","3"] と分解すべきだが、
後者は["-3","*","2"] と分解しなければならない。

#!/usr/bin/ruby -Ks

require "strscan"

class SimpleFormula

# 字句解析を行い、数式文字列を字句の配列(中置記法)に変換する
def formula_to_infix(formula)
infix_array = Array.new
sign = "" # 単項演算子の符号を覚えておく変数
may_sign = true # 単項演算子の符号が現れる可能性があるときtrue
s = StringScanner.new(formula)
while !s.eos?
case
when s.scan(/(\*|\/|\(|\))/)
# ×、/、左括弧と右括弧の場合
infix_array << s[1]
may_sign = true
when s.scan(/(\+|\-)/)
# +と-の場合
if may_sign then
sign = s[1]
else
infix_array << s[1]
end
when s.scan(/(\d+)/)
# 符号のついていない数値が見つかった場合
infix_array << sign + s[1]
sign = ""
may_sign = false
else
raise "error #{s.rest}"
end
end
infix_array
end



(2) 中置記法(infix notation)を後置記法(postfix notation)に変換する。

# 中置記法(infix notation)を後置記法(postfix notation)に変換する
def infix_to_postfix(infix_array)
output = Array.new
ope_stack = Array.new
infix_array.each { |token|
if token == '(' then
# 左括弧が見つかったらスタックへ覚えておく
ope_stack.push(token)
elsif token == ')' then
# 右括弧が見つかったら、
       # 左括弧が見つかるまでスタックから取り出して出力
while ope_stack.size > 0 do
ope = ope_stack.pop
break if ope == '('
output << ope
end
elsif '*|/'.split('|').include?(token) then
# ×と/が見つかったら、
# ×と/が見つかるうちはスタックから取り出して出力してから、
# スタックへ覚えておく
while ope_stack.size > 0 && '*|/'.split('|').include?(ope_stack.last) do
ope = ope_stack.pop
output << ope
end
ope_stack.push(token)
elsif '+|-'.split('|').include?(token) then
# +と-が見つかったら、
# +と-と×と/が見つかるうちはスタックから取り出して出力してから、
# スタックへ覚えておく
while ope_stack.size > 0 && '+|-|*|/'.split('|').include?(ope_stack.last) do
ope = ope_stack.pop
output << ope
end
ope_stack.push(token)
elsif /(\-{0,1}\d+)/ =~ token then
# 数値はそのまま出力
output << token
else
printf "LINE#{__LINE__}: token error [#{token}] \n"
raise "error #{token}"
end
}
# スタックから全て取り出して出力
while ope_stack.size > 0 do
output << ope_stack.pop
end
output
end


中置記法から後置記法へ
例1
入力スタック出力解説
2 2数値はそのまま出力
++ 演算子はスタックへ
3 3数値はそのまま出力
*+ **と比べて優先順位が高いか等しい演算子を出力してからスタックへ
何も出力せずに*をスタックへ
4 4数値はそのまま出力
  *
+
文字列が終わったのでスタックを全部出力
例2
入力スタック出力解説
2 2数値はそのまま出力
** 演算子はスタックへ
3 3数値はそのまま出力
++*+と比べて優先順位が高いか等しい演算子を出力してからスタックへ
*を出力して+をスタックへ
4 4数値はそのまま出力
  +文字列が終わったのでスタックを全部出力

例3

入力スタック出力解説
((左括弧はスタックへ
2 2数値はそのまま出力
+( + 演算子はスタックへ
3 3数値はそのまま出力
)+左括弧が出てくるまでスタックを出力
**演算子はスタックへ
4 4数値はそのまま出力
  *文字列が終わったのでスタックを全部出力

例4
入力スタック出力解説
2 2数値はそのまま出力
** 演算子はスタックへ
(* (左括弧はスタックへ
3 3数値はそのまま出力
+* ( +演算子はスタックへ
4 4数値はそのまま出力
)*+左括弧が出てくるまでスタックを出力
  *文字列が終わったのでスタックを全部出力


(3) 後置記法に変換したものを、前から順番に計算して値を求める。
# 後置記法(postfix notation)を計算して値を求める
def calc_postfix(postfix_array)
stack = Array.new
postfix_array.each { |token|
case token
when "+" then
r = stack.pop
l = stack.pop
stack.push(l + r)
when "-" then
r = stack.pop
l = stack.pop
stack.push(l - r)
when "*" then
r = stack.pop
l = stack.pop
stack.push(l * r)
when "/" then
r = stack.pop
l = stack.pop
if r != 0 then
stack.push(l / r)
else
# ゼロで割っちゃだめ。
p postfix_array
raise "divided by zero"
end
else
stack.push(token.to_i)
end
}
result = stack.pop
end


後置記法に変換したものを、前から順番に計算して値を求める。
例5
入力スタック出力解説
22 数値はスタックへ
32 3 数値はスタックへ
+5 スタックから2つ取り出して足してスタックへ
45 4 数値はスタックへ
*20 スタックから2つ取り出して掛けてスタックへ
  20スタックの一番上が答え



(4) (1)~(3)を連続して呼び出して数式を計算する。
def calc(formula)
infix_array = formula_to_infix(formula)
postfix_array = infix_to_postfix(infix_array)
result = calc_postfix(postfix_array)
end



思いつきのテスト

if __FILE__ == $0
formula_array = [
"2+3*4",
"2*3+4",
"2*3*4",
"(-5)",
"(3+4)",
"2*(3+4)",
"2+(3-4)*5",
"(3-4)*5",
"(-3-4)*5",
"(3-4)*(-5)",
"(-3-4)*-5",
"(-3-4)*-5-35",
"(-3-4)*-5*2",
"2*(3+4)",
"2/3",
"(3*8)/(8-2)",
]

formula = SimpleFormula.new
formula_array.each { |f|
calc_value = formula.calc(f)
eval_value = eval(f)
printf("%12s = %4d %4d\n", f, calc_value, eval_value)
if calc_value != eval_value then
raise "calc error"
end
}
end



実行結果
2+3*4 = 14 14
2*3+4 = 10 10
2*3*4 = 24 24
(-5) = -5 -5
(3+4) = 7 7
2*(3+4) = 14 14
2+(3-4)*5 = -3 -3
(3-4)*5 = -5 -5
(-3-4)*5 = -35 -35
(3-4)*(-5) = 5 5
(-3-4)*-5 = 35 35
(-3-4)*-5-35 = 0 0
(-3-4)*-5*2 = 70 70
2*(3+4) = 14 14
2/3 = 0 0
(3*8)/(8-2) = 4 4


これを種にして、あれこれ拡張し、関数型プログラミング言語の研究をしてみるつもり。
プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示