四則演算のパーサー(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行程度で書けています。