[Python] 中置記法から後置記法への書き換え

四則演算のみを考えます。

こちらを参照しています。

前置記法・中置記法・後置記法

中置記法 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になります。

後置記法の評価とスタック

スタックを用いることで、上の計算を簡潔に表現することができます。

左側から式を見ていって…

1.オペランドの場合はスタックに入れる。

2.オペレーターの場合はスタックから2つ値を取り出して演算して、演算結果をスタックに入れる。

3.式の一番右側に到着したら終了。答えはスタックの中。

このアルゴリズムを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))

中置記法から後置記法への変換

スタックを用いて式を左から右に順番に評価していくことで、中置記法から後置記法へ変換することができる、便利なアルゴリズムがあります。

括弧無しの変換

アルゴリズム

左側から式を見ていって…

1.オペランドの場合は後置記法へ入れる。

2.オペレーターの場合は…

(i) スタックが空ならスタックに入れる。

(ii) スタックが空で無ければ、スタックの一番上のオペレーターと式のオペレータの優先度を比較する。

式のオペレーターの方が優先度が高い場合は、スタックに入れる。

スタックの一番上のオペレータの方が優先度が高い場合は、スタックから全て取り出し、後置記法へ入れる。最後に式のオペレーターをスタックに入れる。

3.式の最後まで行ったら、スタックに入っているオペレーターを取り出して、後置記法へ入れる。

具体例

中置記法 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*-] スタック[]

後置記法への変換が終了しました。

括弧を含む変換

アルゴリズム

左側から式を見ていって…

1.オペランドの場合は後置記法へ入れる。

2.オペレーターの場合は…

(i) スタックが空ならスタックに入れる。

(ii) ‘(‘ ならスタックに入れる。

(iii) ‘)’ならスタックの一番上が ‘(‘ になるまで取り出し、後置記法へ入れる。スタックの一番上に残る ‘(‘ は削除する。

(iv) スタックの一番上のオペレーターと式のオペレータの優先度を比較する。

式のオペレーターの方が優先度が高い場合は、スタックに入れる。

スタックの一番上のオペレータの方が優先度が高い場合は、スタックから ‘(‘ が出るか、または全てなくなるまで取り出して、後置記法へ入れる。最後に式のオペレーターをスタックに入れる。

3.式の最後まで行ったら、スタックに入っているオペレーターを取り出して、後置記法へ入れる。

具体例

中置記法((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))