CodeIQ:ちょっと奇妙な足すと引く

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ちょっと奇妙な足すと引く」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
【概要】
ここはとある遠い世界。この世界にも数式があり、足し算と引き算があります。
  19+2-3-4
こんな具合。この式を、我々の世界では
  ((19+2)-3)-4
と解釈して
  19+2-3-4 = 14
とするけど、この世界では
  19+(2-(3-4))
と解釈して
  19+2-3-4 = 22
となります。
要するに、「+と-の優先順位は同じで両方とも右結合」ということです。
で。
数式を与えます。この世界のルールで計算してください。

【入出力】
入力は
19+2-3-4
のような感じです。

演算子は+と-しか登場しません。括弧があることもあります。
1-4のように、計算結果が負の値になる場合には、我々の世界と同様に数字の前に「-」をつけて-3のようにしてください。
そうそう。言い忘れていましたが、数字はこの世界でも 10進数で、同じ記号を使います。

出力は計算結果になります。
【例】
入力出力
19+2-3-422
1-4-3
2-(2-2)-24

【補足】
不正な入力に対処する必要はありません。
入力文字列の長さは、1〜32 文字です。
入力に含まれる数は、十億以下 です。
入力文字列に、符号を示すマイナスは含まれません。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 入力値をフラットな配列(数値部分と演算子とカッコ)にする
# 数値部分は文字列のまま返る
def toArray(line)
	ret = []
	buf = ""

	for i in 0..line.size
		if (i==line.size) then
			if !buf.empty? then ret << buf end
			break
		end

		if line[i] =~ /[0-9]/ then buf += line[i]
		else
			if !buf.empty? then ret << buf end
			ret << line[i]
			buf = ""
		end
	end

	return ret
end

# カッコ内を部分配列にした形式にパースする
# 引数は入力値をフラットな配列にしたもの
# ex) [1,"-","(",2,"-","(",3,"-",4,")",")","+",5] は [1,"-",[2,"-",[3,"-",4]],"+",5] になる
def parse(arr)
#	p arr	# DEBUG
	ret = []

	while !arr.empty?
		buf = arr.shift
		if buf != "(" then
			if buf =~ /\d+/ then ret << buf.to_i
			else ret << buf
			end
		else
			nxt = []
			cnt = 1

			# 対応する")"まで取り出す
			while true
				nbuf = arr.shift
				if nbuf == "(" then cnt += 1
				elsif nbuf == ")" then cnt -= 1
				end

				if cnt == 0 then
					ret << parse(nxt)
					break
				else nxt << nbuf
				end
			end
		end
#		p ret	#DEBUG
	end

	return ret
end

# 右結合で計算する
def calc(left, op, right)
	case op
	when "+"
		return left + right
	when "-"
		return left - right
	else
		return nil
	end
end

# パース後の配列を計算する
def solve(arr)
	right = nil
	left = nil
	op = nil

	while !arr.empty?
		if right == nil then
			right = arr.pop
			if right.is_a?(Array) then right = solve(right) end
		elsif op == nil then
			op = arr.pop
		elsif left == nil then
			left = arr.pop
			if left.is_a?(Array) then left = solve(left) end
		end

		if (right != nil) && (op != nil) && (left != nil) then
			right = calc(left, op, right)
			op = nil
			left = nil
		end
	end

	return right
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	arr = toArray(line)
	parsed = parse(arr)
	p solve(parsed)
end

解説

見た目より難しい問題です。何が難しいかというと構文木を作らないといけないのが難しいです。これまでもこの手の関数電卓系の問題は何問かありましたが、今までは構文木を作らず適当にごまかしてきました。この問題ではさすがに構文木を作らないわけには行かず、真面目にやっています。

考え方

先述の通り構文木を作ってしまえば、あとは右結合で計算するだけです。なので、どうやって構文木を作るのかが一番のポイントです。
Rubyでやっているので配列を使って表すことにしました。
例えば1+2-(3+(4-5))は[1,"+",2,"-",[3,"+",[4,"-",5]]]と表現します。
Rubyのような動的型付け言語は配列の要素に異なる型の値を入れることができるので、このような持ち方が容易に実現できます。

このように表現すると何が便利かというと、処理を次のように単純化できます。右結合の計算は演算子の左右の値を一時変数に保持する必要ちょっと面倒なので左結合で説明します。
  1. 返却値を0、演算子変数を"+"で用意しておく。
  2. 要素を1つ取り出す。
    • 数値なら返却値と演算子変数に従って加減算する。
    • 演算子なら演算子変数を更新する。
    • 配列ならその配列を引数に本処理を再帰的に呼び出し、結果を演算子変数に従って加算する。
  3. すべての要素分2の処理を繰り返し、返却値を返す。
1+2-(3+(4-5))をこれに従って(左結合で)計算すると次のようになります。
処理対象は[1,"+",2,"-",[3,"+",[4,"-",5]]]です。
  1. 返却値=0、演算子変数="+"で初期化する。
  2. 1を取り出し返却値と加減算し、返却値=1。
  3. "+"を取り出し演算子変数を更新し、演算子変数="+"。
  4. 2を取り出し返却値と加減算し、返却値=3。
  5. "-"を取り出し演算子変数を更新し、演算子変数="-"。
  6. [3,"+",[4,"-",5]]を取り出し、再帰的に処理を呼び出す。
    1. 返却値=0、演算子変数="+"で初期化する。
    2. 3を取り出し返却値と加減算し、返却値=3。
    3. "+"を取り出し演算子変数を更新し、演算子変数="+"。
    4. [4,"-",5]を取り出し、再帰的に処理を呼び出す。
      1. 返却値=0、演算子変数="+"で初期化する。
      2. 4を取り出し返却値と加減算し、返却値=4。
      3. "-"を取り出し演算子変数を更新し、演算子変数="-"。
      4. 5を取り出し返却値と加減算し、返却値=-1。
      5. これ以上要素がないので返却値=-1をリターン。
      返ってきた-1を返却値に加減算し、返却値=2。
    5. これ以上要素がないので返却値=2をリターン。
    返ってきた2を返却値に加減算し、返却値=1。
  7. これ以上要素がないので返却値=1をリターン。
問題は右結合なので配列を末尾から取り出すのと、演算子の左の値に右の値を加減算しなければならない(右側の値に左側の値を加減算するとダメ)のでもう少し手間がかかりますが同じ考え方で計算できます。

main

入力値を取得し、toArray()で一旦フラットな配列にします。例えば「2+(2+2)+2」なら["2","+","(","2","+","2",")","+","2"]にします。
parse()でこれを構文木に直します。[2,"+",[2,"+",2],"+",2]になります。
solve()で計算し、結果を印字します。

toArray(line)

数値と記号を分割するため、入力値をフラットな配列にします。
1文字ずつループし(9〜21行目)、数字なら後続が数字の場合連結するためバッファリングします(15行目)。記号ならバッファに値があればまず、返却用の配列に追加し、続けて現在の文字を追加し、バッファを空にします(16〜20行目)。
これだけだと最後が数字の場合に返却用の配列に追加されないので、lineの文字数+1の要素までカウンタを回し、カウンタが文字数と同じ場合にバッファに値があれば返却用の配列に追加します(10〜13行目)。C言語なら文字列の末尾の0になった場合にこれを行えば良いのですが、Rubyはそれができないのでこのように処理しています。

parse(arr)

フラットな配列に分解した入力値を構文木に直します。
対象の配列arrが空になるまでループします(33〜58行目)。
先頭の要素を取り出し(34行目)、左カッコ"("でなければ返却用の配列retに追加します。この時、要素が数字なら数値に変換し、そうでなければそのまま追加します(35〜38行目)。
取り出した要素が左カッコ"("なら対応する右カッコ")"まで取り出し、parse()を再帰的に呼び出します(39〜56行目)。カッコがネストしている可能性があるので、取り出した要素が左カッコ"("からカウンタを加算、右カッコ")"なら減算します(46〜48行目)。カウンタは1始まりなので0になった時点で最初に見つけた左カッコ"("に対応する右カッコ")"に到達したことになるので、そこまでの部分配列でparse()を再帰呼び出しし、返り値をretに追加します(50〜54行目、54行目の処理は正しい入力値なら不要で到達しないはずの処理)。
33行目からのループを抜けたらretを返します。

solve()

構文木から答えを計算します。
変数rightは演算子の右の値を保持する変数で最終的に答えになります。
変数leftは演算子の左側の値を保持する変数です。
opは演算子を保持する変数です。
なぜ、rightとleftが必要かというと、構文木の要素は末尾から取り出しますが、取り出した要素の計算は普通に左+(-)右だからです。例えば[1,"-",2]として単純に末尾から取り出した値に次の値を順に計算すると2-1=1になってしまい、間違いです。2つの値の計算は普通に左+(-)右とするため変数が必要になります。

82〜90行目の処理で取り出した値を対応する変数に保持します。最初の3要素はright、left、opともにnilなので右の値、演算子、左の値の順番に3要素は取得し、以降はrightを繰り越し、opとleftを更新しながら計算を繰り返します。
rightとleftで取り出した要素が配列なら、その配列でsolve()を再帰的に呼び出して結果をrightかleftに保持します(84行目、89行目)。これによって(カッコ)内を先に計算することができます。

right、op、leftが値を持っていれば計算できるので計算し、結果でrightを更新します。leftとopは次の値を取得するためnilでクリアします(92〜96行目)。
計算はeval()でも良い気がしましたがcalc()関数を用意して計算しました。

最終的にrightの値が答えになるのでこれを返します。

calc(left, op, right)

演算子opに従って計算するだけの関数です。特に説明は不要でしょう。

雑感

構文木は新入社員研修で話だけ聞いた記憶があります。確か、二分木を作って末端のノードには値、途中のノードには演算子を置いて、左下の要素から再帰的にノードをたどることで計算するような話だったような。でも、それ以来構文木を作って処理するようなプログラムを作ったことはなく、今回が初めてだと思います。
で、構文木の作り方をネットで調べてみたのですがあまりわかりやすいのが見つからず、結局自分で考えてこのような実装になりました。Rubyだったので単純にできましたがJavaやC/C++のような強い型付けの言語だったらどうするかなぁと。今回の構文木で保持する値(数値、演算子、配列)をラップするクラス(構造体)を作って、その配列を扱うのが簡単でしょうか?