私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ちょっと奇妙な足すと引く」（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-4 22 1-4 -3 2-(2-2)-2 4
【補足】
不正な入力に対処する必要はありません。
入力文字列の長さは、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のような動的型付け言語は配列の要素に異なる型の値を入れることができるので、このような持ち方が容易に実現できます。
入力値を取得し、toArray()で一旦フラットな配列にします。例えば「2+(2+2)+2」なら["2","+","(","2","+","2",")","+","2"]にします。
parse()でこれを構文木に直します。[2,"+",[2,"+",2],"+",2]になります。
solve()で計算し、結果を印字します。
数値と記号を分割するため、入力値をフラットな配列にします。
1文字ずつループし（9〜21行目）、数字なら後続が数字の場合連結するためバッファリングします（15行目）。記号ならバッファに値があればまず、返却用の配列に追加し、続けて現在の文字を追加し、バッファを空にします（16〜20行目）。
これだけだと最後が数字の場合に返却用の配列に追加されないので、lineの文字数+1の要素までカウンタを回し、カウンタが文字数と同じ場合にバッファに値があれば返却用の配列に追加します（10〜13行目）。C言語なら文字列の末尾の0になった場合にこれを行えば良いのですが、Rubyはそれができないのでこのように処理しています。
フラットな配列に分解した入力値を構文木に直します。
対象の配列arrが空になるまでループします（33〜58行目）。
先頭の要素を取り出し（34行目）、左カッコ"("でなければ返却用の配列retに追加します。この時、要素が数字なら数値に変換し、そうでなければそのまま追加します（35〜38行目）。
取り出した要素が左カッコ"("なら対応する右カッコ")"まで取り出し、parse()を再帰的に呼び出します（39〜56行目）。カッコがネストしている可能性があるので、取り出した要素が左カッコ"("からカウンタを加算、右カッコ")"なら減算します（46〜48行目）。カウンタは1始まりなので0になった時点で最初に見つけた左カッコ"("に対応する右カッコ")"に到達したことになるので、そこまでの部分配列でparse()を再帰呼び出しし、返り値をretに追加します（50〜54行目、54行目の処理は正しい入力値なら不要で到達しないはずの処理）。
33行目からのループを抜けたらretを返します。
構文木から答えを計算します。
変数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の値が答えになるのでこれを返します。
演算子opに従って計算するだけの関数です。特に説明は不要でしょう。
構文木は新入社員研修で話だけ聞いた記憶があります。確か、二分木を作って末端のノードには値、途中のノードには演算子を置いて、左下の要素から再帰的にノードをたどることで計算するような話だったような。でも、それ以来構文木を作って処理するようなプログラムを作ったことはなく、今回が初めてだと思います。
で、構文木の作り方をネットで調べてみたのですがあまりわかりやすいのが見つからず、結局自分で考えてこのような実装になりました。Rubyだったので単純にできましたがJavaやC/C++のような強い型付けの言語だったらどうするかなぁと。今回の構文木で保持する値（数値、演算子、配列）をラップするクラス（構造体）を作って、その配列を扱うのが簡単でしょうか？