Rubyを使った式計算プログラム入門

はじめに

ほとんど全てのインタプリタでは計算式を入力するとその値が返ってきます

例えば
3+5を入力すると8が返り
5*6を入力すると30が返ります

上記のようなプログラムを作る時
上の例であれば左から演算していけばいいのですが
「+」や「*」の演算順序や「( )」がある場合を考えると
演算の順序が異なるので左から演算しても正しい値になりません

例えば
3+5*6を左から演算すると8*6となり48ですが
正しくは3+30と掛け算を優先させないといけないので33と出力すべきです

このように計算順序が入れ替わったときの計算法について書きます
(eval関数を使えばいいんですが,今回は仕組みを考えていきたいので使いません)

計算法

「*」や「/」で計算した集まりを「項」とすると
「項」を「+」や「-」で計算した集まりが「式」となります
そして「( )」の中には「式」があります
つまり
「式」:=「項」[「+」or「-」]「項」[「+」or「-」] ・・・
「項」:=「値」[「*」or「/」]「値」[「*」or「/」] ・・・
「値」:=[「0-9」or「(」「式」「)」]
として計算していきます

イメージ

ペイントで3分クオリティですがこんな感じです

処理順に見ると
1. exprのフェーズで「+」「-」で分解してtermに渡します
2. termのフェーズで「*」「/」で分解してfactに渡します
3. factのフェーズで値だったらtermにその値を戻します(->4.)「()」ならexprに渡します(->1.)
4. termのフェーズで「*」「/」の部分集合を演算してexprに戻します
5. exprのフェーズで「+」「-」の部分集合(最後は式全体)を演算して答えを返します

サンプルコード

calc.rb

class MyCalc
  def initialize(s)
    @s = s
    @p = 0
  end

  def run
    @p=0
    return self.expr
  end

  def expr
    v1 = term
    while(@s[@p] == '+' || @s[@p] == '-')
      op = @s[@p]
      @p += 1
      v2 = term
      v1 = op == "+" ? v1 + v2 : v1 - v2
    end
    return v1
  end

  def term
    v1 = fact
    while(@s[@p] == '*' || @s[@p] == '/')
      op = @s[@p]
      @p += 1
      v2 = fact
      v1 = op == "*" ? v1 * v2 : v1 / v2
    end
    return v1
  end

  def fact
    value = 0
    if @s[@p] =~ /\A-?\d*\Z/
      while @s[@p] =~ /\A-?\d*\Z/
        value = value * 10 + @s[@p].to_i
        @p+=1
      end
    else
      @p+=1
      value = expr
      @p+=1
    end
    return value
  end
end


#### Main ####

while (s=gets.chomp)!='q'
  mc = MyCalc.new(s)
  puts mc.run
end

式をスペースなしで入力すれば計算してくれます
ただし演算子は「+」「-」「*」「/」「(」「)」にしか対応してません
お好みで拡張してください
qが入力するまで繰り返します

プログラムはポインタもどきを進めていって
等優先度の演算を左に結合していき終わったら上の関数に渡していくという
再帰関数で処理していってます

反省点

上のプログラムだと空白文字に対応していません
ちゃんとトークンごとに分解して計算するようにした方がいいかもしれません