四則演算のパーサー(Ruby)

ある問題を解いていて、四則演算のパーサーってどんな風に書くのだろうと思って考えてみました。いわゆる「逆ポーランド記法」にパースできればあとは簡単なので、その方針で考えたのですが、自力ではちょっと荷が重かったですね。ということで検索してみたところ、既に「操車場アルゴリズム」というのがあることを知りました。なんでもあのダイクストラが考えたそうで、いや、すごいですねえ。


解説は上のリンク(Wikipedia)が充分詳しいです。Ruby コードに落としてみたのが以下です。
四則演算のパーサー(Ruby) · GitHub
メソッド parse()逆ポーランド記法を出力するパーサー、メソッド calculate()逆ポーランド記法を処理して実際に計算をします。


使い方はこんな感じです。四則演算の記号 + - * / と括弧(ネスト可)が使えます。演算の優先順位はもちろん通常のもの(掛け算・割り算が足し算・引き算に優先する)です。最後に = をつけます。なお、不正な記法のチェックはしていません。Runtime Error が出るか、正しくない答えが出るかのいずれかの筈です。

$ pry
[1] pry(main)> require_relative "operations_parser"
=> true
[2] pry(main)> parsed = parse("(1 + 5) * 3 - 10 / 2 =")
=> ["1", "5", "+", "3", "*", "10", "2", "/", "-"]
[3] pry(main)> calculate(parsed)
=> 13
[4] pry(main)> parsed = parse("2 * 3 - (10 + 6 / 2) =")
=> ["2", "3", "*", "10", "6", "2", "/", "+", "-"]
[5] pry(main)> calculate(parsed)
=> -7
[6] pry(main)> parsed = parse("(1.5 / (4 - 3) + 1) * 0.5 + 1.7 =")
=> ["1.5", "4", "3", "-", "/", "1", "+", "0.5", "*", "1.7", "+"]
[7] pry(main)> calculate(parsed)
=> 2.95

 
いや、操車場アルゴリズムってよくできていますね。パーサーの部分は 30行程度で書けています。