四則演算のみを考えます。
前置記法・中置記法・後置記法
中置記法 infix
中置記法 infix は普通の式の書き方です。
$$ 1 + 2 $$
$$ A – B $$
$$ x + y * 5 $$
より抽象的に、中置記法 infix を以下のように表現します。
<オペランド operand> <オペレーター operator > <オペランド openrad>
オペランド（被演算子）は演算の対象になるもの、 オペレーター （演算子）は演算を行うものです。
1 + 2 では、1、2はオペランド、+ はオペレーターです。
オペランドが真ん中にあるので、中置記法 infix と呼びます。
オペレーター/演算子には優先順位があり、（）で囲まれたものの優先順位が一番高く、×と÷が2番目の優先順位、＋と―は優先順位が最も低くなります。
式は オペレーター/演算子の優先順位に従いながら、左側から右側へ評価を行います。
前置記法 prefix ポーランド記法
中置記法で必要だった()を使わずとも式を表現できる記法です。
ポーランドの人が開発したので、ポーランド記法と呼ばれます。
$$ + 1 2$$
$$- A B$$
$$+ x * y 5$$
前置記法 prefix という名前の通り、 オペレーター/演算子 が先頭に置かれて、以下のように表現されます。
<オペレーター operator > <オペランド operand> <オペランド openrad>
中置記法 1 + 2 は、前置記法 + 1 2 となります。
中置記法 x + y * 5 は、x + z と、z = y * 5として分けて考えます。
x + z を + x z 、z = * y 5 とそれぞれ前置記法で表現できるので、まとめると + x * y 5 となります。
後置記法 postfix 逆ポーランド記法
コンピュータにとって計算しやすいように開発されました。
ポーランド記法の逆なので、逆ポーランド記法とも呼ばれます。
$$ 1 2 + $$
$$ A B – $$
$$ x y 5 * + $$
後置記法 postfix という名前の通り、 オペレーター/演算子 は一番最後に置かれます。
<オペランド operand> <オペランド openrad> <オペレーター operator >
中置記法 1 + 2 は、後置記法 1 2 + となります。
中置記法 x + y * 5 は、x + z と、z = y * 5として、前置記法と同じように分けて考えます。
x + z を x z + 、z = y 5 *とそれぞれ後置記法で表現できるので、まとめると x y 5 * + となります。
後置記法の評価方法
後置記法の式が与えられた場合の式の評価方法を考えます。
後置記法 2 3 * 5 4 * + 9 – の式を計算してみます。
式を左側から見ていき、 <オペランド operand> <オペランド openrad> <オペレーター operator > の順番に当てはまるものが見つかれば、その式を評価します。
2 3 * 5 4 * + 9 –
左から見ていくと、 2 3 * が <オペランド operand> <オペランド openrad> <オペレーター operator > に当てはまるので、評価して6になります。
6 5 4 * + 9 –
左から見ていくと、 5 4 * が <オペランド operand> <オペランド openrad> <オペレーター operator > に当てはまるので、評価して20になります。
6 20 + 9 –
左から見ていくと、 6 20 + が <オペランド operand> <オペランド openrad> <オペレーター operator > に当てはまるので、評価して26になります。
26 9 –
左から見ていくと、 26 9 – が <オペランド operand> <オペランド oppnrad> <オペレーター operator > に当てはまるので、評価して17になります。
17
これ以上評価できないので、答えは17になります。
後置記法の評価とスタック
スタックを用いることで、上の計算を簡潔に表現することができます。
左側から式を見ていって…
１．オペランドの場合はスタックに入れる。
２．オペレーターの場合はスタックから2つ値を取り出して演算して、演算結果をスタックに入れる。
３．式の一番右側に到着したら終了。答えはスタックの中。
このアルゴリズムをPythonで書きます。
式は文字列で、オペレーター、オペランドそれぞれの間はスペースで区切られているとします。
def postfix_eval(str_expression):
lst_operators = ['+', '-', '*', '/']
stack = []
for char in str_expression.split():
if char in lst_operators:
operand2 = stack.pop()
operand1 = stack.pop()
# オペランドの順番に注意
exp = operand1 + char + operand2
result = eval (exp)
stack.append(str(result))
else:
stack.append(char)
return stack[-1]
str_expression = '2 3 * 5 4 * + 9 -'
print(postfix_eval(str_expression))
中置記法から後置記法への変換
スタックを用いて式を左から右に順番に評価していくことで、中置記法から後置記法へ変換することができる、便利なアルゴリズムがあります。
括弧無しの変換
アルゴリズム
左側から式を見ていって…
１．オペランドの場合は後置記法へ入れる。
２．オペレーターの場合は…
(i) スタックが空ならスタックに入れる。
(ii) スタックが空で無ければ、スタックの一番上のオペレーターと式のオペレータの優先度を比較する。
式のオペレーターの方が優先度が高い場合は、スタックに入れる。
スタックの一番上のオペレータの方が優先度が高い場合は、スタックから全て取り出し、後置記法へ入れる。最後に式のオペレーターをスタックに入れる。
３．式の最後まで行ったら、スタックに入っているオペレーターを取り出して、後置記法へ入れる。
具体例
中置記法 A + B * C – D * E という式を後置記法に変換してみます。
Aは後置記法に入れます。
中置記法[+B*C-D*E] 後置記法[A] スタック[]
+はスタックに入れます。
中置記法 [B*C-D*E] 後置記法[A] スタック[+]
Bは後置記法に入れます。
中置記法 [*C-D*E] 後置記法[AB] スタック[+]
*は+と比較すると、*の方が優先度が高いので、スタックに入れます。
中置記法 [C-D*E] 後置記法[AB] スタック[+*]
Cは後置記法に入れます。
中置記法 [-D*E] 後置記法[ABC] スタック[+*]
-は*と比較すると、*の方が優先度が高いので、スタックから全て取り出し後置記法に加え、最後に-をスタックに入れます。
中置記法 [D*E] 後置記法[ABC*+] スタック[-]
Dは後置記法に入れます。
中置記法 [*E] 後置記法[ABC*+D] スタック[-]
*は-と比較すると、*の方が優先度が高いので、スタックに入れます。
中置記法 [E] 後置記法[ABC*+D] スタック[-*]
Eは後置記法に入れます。
中置記法 [] 後置記法[ABC*+DE] スタック[-*]
スタックに残っているオペレーターを取り出して、後置記法に入れます。
中置記法 [] 後置記法[ABC*+DE*-] スタック[]
後置記法への変換が終了しました。
括弧を含む変換
アルゴリズム
左側から式を見ていって…
１．オペランドの場合は後置記法へ入れる。
２．オペレーターの場合は…
(i) スタックが空ならスタックに入れる。
(ii) ‘(‘ ならスタックに入れる。
(iii) ‘)’ならスタックの一番上が ‘(‘ になるまで取り出し、後置記法へ入れる。スタックの一番上に残る ‘(‘ は削除する。
(iv) スタックの一番上のオペレーターと式のオペレータの優先度を比較する。
式のオペレーターの方が優先度が高い場合は、スタックに入れる。
スタックの一番上のオペレータの方が優先度が高い場合は、スタックから ‘(‘ が出るか、または全てなくなるまで取り出して、後置記法へ入れる。最後に式のオペレーターをスタックに入れる。
３．式の最後まで行ったら、スタックに入っているオペレーターを取り出して、後置記法へ入れる。
具体例
中置記法((A + B) * C – D) * Eを後置記法に変換します。
( はスタックに入れます。
中置記法[(A+B)*C-D)*E] 後置記法[] スタック[(]
( はスタックに入れます。
中置記法[A+B)*C-D)*E] 後置記法[] スタック[((]
Aは後置記法に入れます。
中置記法[+B)*C-D)*E] 後置記法[A] スタック[((]
+はスタックに入れます。
中置記法[B)*C-D)*E] 後置記法[A] スタック[((+]
Bは後置記法に入れます。
中置記法[)*C-D)*E] 後置記法[AB] スタック[((+]
) なのでスタックから( まで取り出し後置記法に入れ、スタックの頂上に残る(を削除します。
中置記法[*C-D)*E] 後置記法[AB+] スタック[(]
*なのでスタックに入れます。
中置記法[C-D)*E] 後置記法[AB+] スタック[(*]
Cなので後置記法に入れます。
中置記法[-D)*E] 後置記法[AB+C] スタック[(*]
-と*を比較すると*の方が優先度が高いので、スタックから*を鳥刺し後置記法に入れて、スタックに-を入れます。
中置記法[D)*E] 後置記法[AB+C*] スタック[(-]
Dなので後置記法に入れます。
中置記法[)*E] 後置記法[AB+C*D] スタック[(-]
) なので、スタックから( まで取り出し後置記法に入れ、スタックの頂上に残る( を削除します。
中置記法[*E] 後置記法[AB+C*D-] スタック[]
*はスタックが空なのでスタックに入れます。
中置記法[E] 後置記法[AB+C*D-] スタック[*]
Eなので後置記法に入れます。
中置記法[] 後置記法[AB+C*D-E] スタック[*]
スタックに残っているオペレーターを後置記法に入れます。
中置記法[] 後置記法[AB+C*D-E*] スタック[]
変換が終了しました。
Pythonのコード
このアルゴリズムをPythonで書きます。
オペレーター、オペランドはスペースで区切った文字列で与えます。
operator_precedence = {
'(' : 0,
')' : 0,
'+' : 1,
'-' : 1,
'*' : 2,
'/' : 2
}
def infix_to_postfix(infix):
stack = []
postfix = []
for char in infix.split():
if char not in operator_precedence:
postfix.append(char)
else:
if len(stack) == 0:
stack.append(char)
else:
if char == "(":
stack.append(char)
elif char == ")":
while stack[len(stack) - 1] != "(":
postfix.append(stack.pop())
stack.pop()
elif operator_precedence[char] > operator_precedence[stack[len(stack) - 1]]:
stack.append(char)
else:
while len(stack) != 0:
if stack[len(stack) - 1] == '(':
break
postfix.append(stack.pop())
stack.append(char)
while len(stack) != 0:
postfix.append(stack.pop())
return postfix
infix = '( ( A + B ) * C - D ) * E'
# ['A', 'B', '+', 'C', '*', 'D', '-', 'E', '*']
print(infix_to_postfix(infix))