逆ポーランド記法に潜む罠 -単項演算子に気をつけろ！-
スクリプトの計算がいつまでも
自前で用意した中間記法*1を根性で処理する
代物なのも、危険極まりない気がしてきたので、
内部的に逆ポーランド記法(以下「RevP」)に書き換えるようにしようかなと思い立ったわけですが。
(結論は一番下です)
…はてさて、何故かはわからないんですが、
単項演算子を用いたRevPな式ってほとんど見ないんですよね。
僕が初めに参考にしていた所だと
と書いてあるわけですが、実際の所どうなのか試してみる。
なお、今回はカッコ以外は全て2項演算子でしたが
単項演算子（符合反転の - とか）の場合でも処理は変わりません。
一応、こんな感じで変換中も書いてみます。
・「-3+4」
[出力分]{演算子のスタック} 「元の式の残り」
…
「3-4+」かな？
[]{-} 「3+4」
[3]{-} 「+4」
[3-]{+} 「4」
[3-4]{+} 「」
[3-4+]{} 「」
…確かに「-」を「数値x1に対して適応できる演算子」(=単項演算子ですが(笑))として扱えればいけそう。
結果は「1」。
・「-3+4*5」
… 積算と組み合わせてみる
「3-45*+」？
[]{-} 「3+4*5」
[3]{-} 「+4*5」
[3-]{+} 「4*5」
[3-]{+} 「4*5」
[3-4]{+} 「*5」
[3-4]{+} 「*5」
[3-4]{+*} 「5」
[3-45]{+*} 「」
[3-45*+]{} 「」
…これも問題なし。
結果は「17」。
・「(-3+4)*(3+5)」
… 括弧と組み合わせてみる
…えー、「3-4+35+*」？
[]{(} 「-3+4)*(3+5)」
[]{(-} 「3+4)*(3+5)」
[3]{(-} 「+4)*(3+5)」
[3-]{(+} 「4)*(3+5)」
[3-4]{(+} 「)*(3+5)」
[3-4+]{} 「*(3+5)」
[3-4+]{*} 「(3+5)」
[3-4+]{*(} 「3+5)」
[3-4+3]{*(} 「+5)」
[3-4+3]{*(+} 「5)」
[3-4+35]{*(+} 「)」
[3-4+35+]{*} 「」
[3-4+35+*]{} 「」
これも問題なく、8が出る。
・「(-3+4)*(-3+5)」
… 後ろの括弧の方に入れてみる
…えーっと、「3-4+3-5+*」かな？
[]{(} 「-3+4)*(-3+5)」
[]{(-} 「3+4)*(-3+5)」
[3]{(-} 「+4)*(-3+5)」
[3-]{(+} 「4)*(-3+5)」
[3-4]{(+} 「)*(-3+5)」
[3-4+]{} 「*(-3+5)」
[3-4+]{*} 「(-3+5)」
[3-4+]{*(} 「-3+5)」
[3-4+]{*(-} 「3+5)」
[3-4+3]{*(-} 「+5)」
[3-4+3-]{*(+} 「5)」
[3-4+3-5]{*(+} 「)」
[3-4+3-5+]{*} 「」
[3-4+3-5+*]{} 「」
……アレ？二回目の「-」が単項演算子か二項演算子かこれでは判別できないんですが…(汗)
ちなみに、素直にやると結果は「3」。(…というか、最後の積算をするのに項が足りない…。)
…さて、それではどうしましょうか…(何)
…要するに、「単項演算子か二項演算子かの判別」が出来ればいいので、
符号関連の「+」「-」を別の記号(…というか演算子)で表すことが出来れば大丈夫そうです。
(ちなみに、C言語の「+」「-」も符号関連と演算関連は別物扱いみたいですね。
(優先度が全く異なる)
…どうやって判別してるんでしょうか(汗))
というわけで、
先程の式の「-」を「_」に置き換えて再計算してみます。
・「(_3+4)*(_3+5)」
… 後ろの括弧の方に入れてみる(改定版)
…えー、変換式は本当に置き換えただけなんですが(汗)
[]{(} 「_3+4)*(_3+5)」
[]{(_} 「3+4)*(_3+5)」
[3]{(_} 「+4)*(_3+5)」
[3_]{(+} 「4)*(_3+5)」
[3_4]{(+} 「)*(_3+5)」
[3_4+]{} 「*(_3+5)」
[3_4+]{*} 「(_3+5)」
[3_4+]{*(} 「_3+5)」
[3_4+]{*(_} 「3+5)」
[3_4+3]{*(_} 「+5)」
[3_4+3_]{*(+} 「5)」
[3_4+3_5]{*(+} 「)」
[3_4+3_5+]{*} 「」
[3_4+3_5+*]{} 「」
「3_4+3_5+*」かな？
…お、コレだと結果はきちんと「2」になりますね。
…というわけで、長ったらしくなりましたが、
逆ポーランド記法だと、符号関連の「+」「-」は別の記号で表現する必要がある。
みたいです。
