Stackによる逆ポーランド記法の計算

概要

逆ポーランド記法とは、演算子を数字の後に記述する記法です。
例えば一般的な数式 (1+2)*(5+4) は、逆ポーランド記法では 1 2 + 5 4 + * と記述されます。
逆ポーランド記法の計算式を標準入力で受け取り、その計算結果を出力するコードをPythonで書いてみます。

例1

入力

1 2 +

出力

3

例2

入力

1 2 + 3 4 - *

出力

-3

例3

入力

34 116 + 20 5 - 5 - 1 * +

出力

160

実装例

逆ポーランド記法で記述された数式は、スタックを用いて計算することができます。
数式を一文字ずつ読み込み、数値ならStackに積む、演算子ならStackから値を2つ取り出して計算結果をStackに積む、という操作を繰り返すことで最終的な計算結果を得ることができます。

s = list(input().split())
stack = []

for i in range(len(s)):
    if s[i] == '+':
        stack.append(stack.pop() + stack.pop())
    elif s[i] == '-':
        stack.append(-(stack.pop() - stack.pop()))
    elif s[i] == '*':
        stack.append(stack.pop() * stack.pop())
    else:
        stack.append(int(s[i]))

print(stack[-1])

参考

Aizu Online Judge