学生エンジニア小話

プログラミングのお話

計算順序を考慮した電卓をRubyで書く

f:id:takuseno:20160924211552j:plain初めての投稿になります。

情報工学科の学部生でアルバイトでフルスタックエンジニアをやっています。

最初の内容は僕がQiitaに書いた、

qiita.com

の話をします。

なぜ計算順序を考慮した電卓を書いたか

僕が今読んでいる本でUnderstanding Computationという本があり、この本の最初の話はプログラミング言語のSemantics(言語学では単語とその単語の意味の関係)をRubyで簡単なプログラミング言語を書きつつ理解するという内容です。

shop.oreilly.com

この章を読み終えるとRubyで簡単な式を評価できるプログラミング言語を作ることができます。この章で学んだものを生かして簡単なものを書きたいなと思った時に計算順序を考慮した電卓でも作ろうかなと思いました。この計算順序を考慮するというのはコンピューターサイエンスのバックグラウンドがあれば式を木構造にして評価するというアイディアは持っていますが、文系エンジニアのような方にはなかなか難しいものがあります。

アルバイト先の会社でたまに勉強会をやっているのでネタ作りも兼ねてこのような基礎的なアイディアと、問題を解決する際にデータ構造を工夫するといいぞといういい見本になるなと思って書きました。

簡単なコード

class Value < Struct.new(:value)
  def evaluate
    value.to_i
  end
end

class Add < Struct.new(:first, :second)
  def evaluate
    first.evaluate + second.evaluate
  end
end

class Sub < Struct.new(:first, :second)
  def evaluate
    first.evaluate - second.evaluate
  end
end

class Mul < Struct.new(:first, :second)
  def evaluate
    first.evaluate * second.evaluate
  end
end

class Div Struct.new(:first, :second)
  def evaluate
    first.evaluate / second.evaluate
  end
end

def parse(equation)
  length = equation.length
  add_pos = equation.rindex('+')
  sub_pos = equation.rindex('-')
  if !add_pos && !sub_pos
    mul_pos = equation.rindex('*')
    div_pos = equation.rindex('/')
    if !mul_pos && !div_pos
      Value.new(equation)
    elsif (!div_pos && mul_pos) || mul_pos > div_pos
      Mul.new(parse(equation[0...mul_pos]), parse(equation[mul_pos + 1..length]))
    else
      Div.new(parse(equation[0...div_pos]), parse(equation[div_pos + 1..length]))
    end
  elsif (!sub_pos && add_pos) || add_pos > sub_pos
    Add.new(parse(equation[0...add_pos]), parse(equation[add_pos + 1..length]))
  else
    Sub.new(parse(equation[0...sub_pos]), parse(equation[sub_pos + 1..length]))
  end
end

print parse('1+2*3-4').evaluate # 3

解説

基本的に後に出てくるものほど最後に計算します。文字列を後ろからパースして最初に出てきた+-木構造のノードにして演算子の左右をそれぞれ再帰的にパースしていきます。+-もなくなったら次は*/をチェックしていきます。もし演算子が見つかれば再び再帰的にパースします。そして演算子がなくなったら葉として値を持ちます。

しかし肝心のポイントはそこではなく、どのように木構造を保持するかです。今回はUnderstanding Computationと同じようにクラスのインスタンスに入れることにしました。演算子のクラスのオブジェクトがノードとなりValueが葉となります。

これをプログラミング意味論的な言い方をするとOpereational Semanticsということができます。Operational Semanticsはプログラムの意味を理解する時にどのようにプログラムが実行されるかというルールを定義することで理解するという意味だそうです。

まとめ

Understanding Computationはコンピューターサイエンスのバックグランドがない人を対象にしているらしいですが、情報工学科の学生でも十分読む価値があります。大学の授業ではなかなかやらないトピックなのでこの本を通して得られる知識はコードの最適化やアルゴリズムを考える上でやくにたつと思います。

実は今年の夏にUC Berkeleyのサマーセッションに出てコンピュータアーキテクチャの授業を受けてきました。他の授業を受けていた同じ学科の友達はPythonについての授業だったそうですが、単なるプログラミングの授業ではなくプログラミング意味論の要素も入っていたようです。このサマーセッションについては別の記事で書きたいと思います。