逆ポーランド記法

逆ポーランド記法

数学的な演算を簡単にするのに逆ポーランド記法があります。

逆ポーランド記法では、「1 + 2」という書き方を「1 2 +」というように演算子を数字の後ろに記述します。

逆ポーランド記法で表現されたものはスタックで処理しやすいという特徴があります。

先頭から順に読み込んで、数であればスタックに積み、演算子であればスタックから値を２つ取り出して計算した結果をまたスタックに積む、という操作を繰り返すだけで計算ができます。

ソースコード

「4 * (8 + 2) - (3 -1) * 4」という数式を逆ポーランド記法で表現すると「4 8 2 + * 3 1 - 4 * -」となります。

これを計算するソースコードは次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def calc(s):
    stack = []
    for i in s.split(' '):
        # スタックの内容を表示
        print(stack)
        if i == '+':
            # +の時はスタックから数字を２つ取り出して加算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a + b)
        elif i == '-':
            # -の時はスタックから数字を２つ取り出して減算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a - b)
        elif i == '*':
            # *の時はスタックから数字を２つ取り出して乗算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a * b)
        elif i == '/':
            # /の時はスタックから数字を２つ取り出して減算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a // b)
        else:
            # 演算子以外（数字）のときはその値を格納する
            stack.append(int(i))
    return stack[0]

print('解：', calc('4 8 2 + * 3 1 - 4 * -'))

[実行結果]

[]

[4]

[4, 8]

[4, 8, 2]

[4, 10]

[40]

[40, 3]

[40, 3, 1]

[40, 2]

[40, 2, 4]

[40, 8]

解： 32

解は 32 となり「4 * (8 + 2) - (3 -1) * 4」の計算結果として正しいことが確認できます。