操車場アルゴリズムで四則計算の数式をパース

以前に簡単な四則計算を再帰下降構文解析でしてみた¹ものの、もっと単純で面白い感じのアルゴリズムがあった気がしていた。調べたら**「操車場アルゴリズム」**（shunting-yard algorithm）と思い出したので、これをRubyで実装してみる。

概要

詳しい説明や図解はWikipedia参照。

中置記法で書かれたよく見る数式を、後置記法（逆ポーランド記法）に変換できる。記号列を入力から出力へ送る際にスタックを用いて並べ替える様子を、列車を並べ替える様子で説明したため、操車場アルゴリズムと呼ばれる。

コード

以前と同様に「1桁の整数・加算・乗算・括弧のみの数式を解釈して計算結果を返す」パーサを作ってみる。各文字がそのままトークンになるので、字句解析を省いて簡略化する²。

エラー処理は不完全なので、前提に合わない数式（例えば2桁の数字）を入力してもエラーにならず変な結果を返すことがある。

expr_parser.rb

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. 色々な再帰の練習としてやったうちの1つ。 → 『再帰的なアルゴリズムの実例集』 ↩

2. 単純な字句解析であれば、正規表現で文字列を区切っていけばいい。 ↩