逆ポーランド記法

中間記法 

よく見る普通の数式の表し方
人間が見る分には理解しやすいよ
(1 + 2) / (3 - 4) = (3) / (-1) = -3

1 + 2 / 3 - 4 　通常括弧を付けて優先度を表すよ

後置記法 

演算記号を数字の後ろに置く計算記法
これが逆ポーランド記法です。
1 + 2 ⇒ 1 2 +
のように、間にあった演算記号を後ろに置く書き方

逆ポーランド記法への変換 

(1 + 2)*((3 + 4)/(5 - 6))
１．優先度の高いカッコの中身順に取り出して、記号に置き換える
ついでに後置記法に直しておく
A = (1+2) = 1 2 +
B = (3+4) = 3 4 +
C = (5-6) = 5 6 -

２．記号で置き換えた式のさらに優先度の高い括弧を取り出して記号に置き換える
A*(B/C)
D = (B/C) = B C /

３．括弧がなくなるまで２．を行う
最後記号2文字と演算記号になるので、後置記法に直す
A*D = A D *

４．記号を元に戻す
A = (1+2) = 1 2 + ・・・①
B = (3+4) = 3 4 + ・・・②
C = (5-6) = 5 6 - ・・・③
D = (B/C) = B C / ・・・④
A D *
 ④式より A (B C /) * →　A B C / *
 ③式より A B 5 6 - / *
 ②式より A 3 4 + 5 6 - / *
 ①式より 1 2 + 3 4 + 5 6 - / *

例題もう一個
( ( a + b ) * c ) – d
A = a + b = a b +
(A * c) - d 
B = A * c = A c *
B - d = Bd -
Bd - = (A c *) d - = ((a b +) c *) d -
= a b + c * d -

逆ポーランド記法から、中間記法への変換

1 2 + 3 4 - /
左から演算記号を見つけ、前の２つの数字を取り出し記号化する
A = 1 2 +
A 3 4 - /
B = 3 4 -
A B /
C = A B /
多分２文字と演算記号は簡単に中間記法になおせるので、直していく
C = A B / 
  = A / B = (1 2 +) / B 
  = (1 + 2) / (3 4 -) 
  = (1 + 2)/(3 - 4)

練習問題

以下の、中間記法の数式を逆ポーランド記法に変換しなさい 

  ⓵ 1 + (2 * (3 - (4 + 5)))
  ⓶ 1 + ((2 - (3 + 4)) * 5)
  ⓷ (1 - (2 + 3)) + (4 * 5)
  ⓸ (((1 + 2) - 3) * 4) + 5

練習問題

１．逆ポーランド表記法（後置表記法）で，“EF-G÷CD-AB+÷+”を中置記法になおせ (平成21年秋期問3) 

   EF-G÷CD-AB+÷+
X = EF- = (E - F)
   XG÷CD-AB+÷+
Y = XG÷ = (X ÷ G)
   YCD-AB+÷+
Z = CD- = (C - D)
   YZAB+÷+
P = AB+ = (A + B)
   YZP÷+
Q = ZP÷ = (Z ÷ P)
   YQ+ = Y + Q
       = (X ÷ G) + (Z ÷ P)
       = ((E-F)÷G)+((C-D)÷(A+B))

２．Y=(A+B)×(C-(D÷E))　を逆ポーランド記法に直せ 

Y=(AB＋) × ( C－ ( DE÷ ))
Y=(AB＋) × ( C(DE)÷－)
Y= ( AB+ )( C ( DE ) ÷－ )×

Y(AB+)(C(DE)÷－)×=

YAB+CDE÷－×＝

３．13 5 4 + 3 / 4 * - * * を中間記法で表せ 

​13  5  4 + 3 / 4 * -
A = 5 4 + = (5+4)
13 A 3 / 4 * -
B = A 3 / = (A/3)
13 B 4 * -
C = B 4 * = (B*4)
13 C -
D = 13 C - = (13 - C)
中間記法に戻していきます。
D = 13-C = 13-(B\*4) = 13-((A/3)*4) = 13 - (((5 + 4) / 3) * 4)
ついでに値を計算してみると
= 13 - (((5+4)/3) * 4)
= 13 - 12 
= 1

スタック使って逆ポーランド記法の計算をしてみる
そのルールは、次の通りです。

  • 逆ポーランド記法で記述された数式を左から順番に処理する。
  • スタックは空であるとする

　　　

  • 数値ならば、Push する
  • 演算子ならば、
    • 記号なしリストスタックの１番上の数値を Pop して、その数値をXとする。
    • スタックの１番上の数値を Pop して、その数値をYとする。
    • このとき、演算子を＠とすると（ {@ : * + / -} )
    • Y @ X を Push

〇 数式がなくなったとき、スタックに残った値が計算結果となる。

このように、逆ポーランド記法では、＋×や（）などの優先順位を考慮する必要がなく、式の解釈が簡単になり、
スタック操作だけで行えるので、初期の電卓では逆ポーランド記法の順に入力するものもありました。
また、コンパイラで数式を解釈するときにも利用されています。


練習問題

逆ポーランド記法で表された数式
13 5 4 + 3 / 4 * -
を上記のスタックを使ったアルゴリズムを使って計算し計算結果を答えなさい。

pop stack 操作 数式 補足
- | -- | -- | -- | -- | -- | -- | 空のスタック 13 5 4 + 3 / 4 * -
- | 13 | -- | -- | -- | -- | -- | Push(13) 13 5 4 + 3 / 4 * -
- | 5 | 13 | -- | -- | -- | -- | Push( 5) 5 4 + 3 / 4 * -
- | 4 | 5 | 13 | -- | -- | -- | Push( 4) 4 + 3 / 4 * -
4 | 5 | 13 | -- | -- | -- | -- | Pop() + 3 / 4 * - 演算子が現れたら２つpop
5 | 13 | -- | -- | -- | -- | -- | Pop() + 3 / 4 * - 演算子が現れたら２つpop
- | 9 | 13 | -- | -- | -- | -- | Push(9) + 3 / 4 * - 5 + 4 popした順に右から並べて間に演算子。結果をpush
- | 3 | 9 | 13 | -- | -- | -- | Push(3) 3 / 4 * -
3 | 9 | 13 | -- | -- | -- | -- | Pop() / 4 * - 演算子が現れたら２つpop
9 | 13 | -- | -- | -- | -- | -- | Pop() / 4 * - 演算子が現れたら２つpop
| 3 | 13 | -- | -- | -- | -- | Push(3) / 4 * - 9 / 3 の結果をPush
| 4 | 3| 13 | -- | -- | -- | Push(4) 4 * -
4 | 3 | 13| -- | -- | -- | -- | Pop() * - 演算子が現れたら２つpop
3 | 13 | --| -- | -- | -- | -- | Pop() * - 演算子が現れたら２つpop
| 12 | 13| -- | -- | -- | -- | Push(12) - 3 * 4 の結果をPush
12 | 13 | -- | -- | -- | -- | -- | Pop() - 演算子が現れたら２つpop
13 | -- | --| -- | -- | -- | -- | Pop() - 演算子が現れたら２つpop
| 1 | --| -- | -- | -- | -- | Push(1) 13 - 12 の結果をpush