応用情報技術者平成28年秋期 午前3
逆ポーランド表記法で表された式を評価する場合，途中の結果を格納するためのスタックを用意し，式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき，入力が演算子となった。このときに行われる演算はどれか。ここで，演算は中置表記法で記述するものとする。
１、逆ポーランド表記法は、
演算子を被演算子の右側に記述する表記法です。
[文字1,演算子,文字2] → [文字1,文字2,演算子] に変えます。
スタックに
ＤＣＢＡとすると、
演算子はＡＢ、文字１はＣ、文字２はＤですね。
逆ポーランド表記法になる前に、Ｃ 演算子 Ｄ でしょう。
例えば、
A＝4×5－6＋3×2
という式を逆ポーランド表記法で記述すると、
A45×6－32×＋＝
となります。
構文木で表すと次のようになります。
この構文木は式の並び順のとおりに「左の葉→右の葉→節」という後行順序で操作が行われます。
問題に戻ると、演算子の前にCとDがスタックに積まれています。つまり先に積まれている「C」が左の葉の値、「D」が右の葉の値ということになります。これを逆ポーランド表記の式にすると「CD演算子」と変換することができます。