以前に簡単な四則計算を再帰下降構文解析でしてみた1ものの、もっと単純で面白い感じのアルゴリズムがあった気がしていた。調べたら「操車場アルゴリズム」（shunting-yard algorithm）と思い出したので、これをRubyで実装してみる。
概要
詳しい説明や図解はWikipedia参照。
中置記法で書かれたよく見る数式を、後置記法（逆ポーランド記法）に変換できる。記号列を入力から出力へ送る際にスタックを用いて並べ替える様子を、列車を並べ替える様子で説明したため、操車場アルゴリズムと呼ばれる。
コード
以前と同様に「1桁の整数・加算・乗算・括弧のみの数式を解釈して計算結果を返す」パーサを作ってみる。各文字がそのままトークンになるので、字句解析を省いて簡略化する2。
エラー処理は不完全なので、前提に合わない数式（例えば2桁の数字）を入力してもエラーにならず変な結果を返すことがある。
class ExprParser
class InvalidToken < RuntimeError; end
class ParenthesisMismatch < RuntimeError; end
# 優先順位が自身以上の演算子の一覧
# （左結合的なら自分自身を含める）
OP_PRECEDENCE = {"+"=>%w[+ *], "*"=>%w[*]}
private_constant :OP_PRECEDENCE
# パーサの動作を設定する
# * nop: 計算を実行せず逆ポーランド記法のまま出力する
def initialize(options = {nop: false})
@options = {}
options.each { |k,v| @options[k.to_sym] = v }
end
# 数式をパースする
# 戻り値は出力の配列（計算済みなら結果のみ格納）
def parse(str)
@output = [] # 出力キュー
@stack = [] # 一時的な置き場：演算子と左括弧を積む
# 文字列からトークンを切り出して、種類ごとに処理する
# （今回は常に1文字＝1トークン）
str.each_char do |c|
case c
# 数値はそのまま @output へ移動する
when /\A\d\z/
@output.push(c.to_i)
# 演算子の場合は、自身以上の優先順位の演算子を
# @stack から予め掃き出し、自身を @stack に積む
when *OP_PRECEDENCE.keys
while OP_PRECEDENCE[c].include?(@stack.last)
@output.push(@stack.pop); operate
end
@stack.push(c)
# 左括弧は @stack に積んでおく
when "("
@stack.push(c)
# 右括弧が来たら、 @stack から左括弧を抜くまで演算子を掃き出す
when ")"
while @stack.last != "("
raise ParenthesisMismatch if @stack.empty?
@output.push(@stack.pop); operate
end
@stack.pop # 左括弧は出力せず捨てる
else
raise InvalidToken
end
end
# 入力が終わったら、 @stack の全演算子を掃き出す
until @stack.empty?
raise ParenthesisMismatch if @stack.last == "("
@output.push(@stack.pop); operate
end
return @output
end
# @stack から @output に移動した際に、計算を実行するための補助メソッド
# オプション nop が真なら実行しない
private def operate
return if @options[:nop]
case (op = @output.pop)
when *OP_PRECEDENCE.keys
num2 = @output.pop
num1 = @output.pop
@output.push(num1.send(op, num2))
else
raise InvalidToken
end
end
end
if $0 == __FILE__
str = "1+2*(3*(4+5)+6)*(7+8)+9"
p ExprParser.new.parse(str) #=> [1000]
p ExprParser.new(nop: true).parse(str)
#=> [1, 2, 3, 4, 5, "+", "*", 6, "+", "*", 7, 8, "+", "*", "+", 9, "+"]
end
後置記法の結果をGhostscriptでも計算してみる。一度に入力せず適宜 pstack を挟めば、その時点でのスタックの内容を見られる。
$ gs -sDEVICE=nullpage
GS> 1 2 3 4 5 add mul 6 add mul 7 8 add mul add 9 add ==
1000
GS> quit
参考：PostScript実習マニュアル 第1章 PostScriptの基礎
メモ
演算子の優先順位を数字でなく直接リストとして与えたので、四則計算程度ならともかく数が増えたら管理が困難になる。（一方で累乗のような右結合性の演算子には対応しやすいはず）
後から調べてみたところ、トークン全般の優先順位の付け方を工夫してもっと統一的に処理できることがわかった。数字に関しても入力から出力へ直接移動させるのではなく、一旦スタックに積むことで他の記号と同じ扱いができる。
https://qiita.com/phenan/items/df157fef2fea590e3fa9
-
色々な再帰の練習としてやったうちの1つ。 → 『再帰的なアルゴリズムの実例集』 ↩
-
単純な字句解析であれば、正規表現で文字列を区切っていけばいい。 ↩