演算式において，+，-，×，÷などの演算子を，演算の対象であるAやBなどの演算数の間に書く「A+B」のような記法を中置記法と呼ぶ。また，「AB+」のように演算数の後に演算子を書く記法を逆ポーランド表記法と呼ぶ。中置記法で書かれる式「(A+B)×(C-D)」を下図のような構文木で表し，これを深さ優先順で，「左部分木，右部分木，節」の順に走査すると得られる「AB+CD-×」は，この式の逆ポーランド表記法となっている。
中置記法で「(A+B÷C)×(D-F)」と書かれた式を逆ポーランド表記法で表したとき，最も適切なものはどれか。
図 (A+B)×(C-D)を表す構文木。矢印の方向に走査し，ノードを上位に向かって走査するとき（●で示す）に記号を書き出す。
① ABC÷+DF-×
② AB+C÷DF-×
③ ABC÷+D×F-
④ ×+A÷BC-DF
⑤ AB+C÷D×F-
解答
①
解説
×÷を+-より優先して式の後ろに記載していくと
(A+B÷C)×(D-F) = (A+BC÷)(D-F)× = (ABC÷+)(DF-)× = ABC÷+DF-×
となり，①が正解であるとわかります。
過去の出題
なし
