逆ポーランド記法 Haskell(Beta)編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

逆ポーランド記法で書かれた数式が与えられます。この数式を計算した結果を出力してください。この問題は少し難しいですが、スタックを用いて解いてみましょう。

逆ポーランド記法とは

私たちがよく用いる数式の記法は中置記法と呼ばれています。たとえば以下の数式のように、数値と数値の間に演算子が置かれます。

1 + 2

逆ポーランド記法では以下の数式のように、数値と数値の後に演算子が置かれます。

1 2 +

逆ポーランド記法の長所として、計算順序を決定する括弧を必要としません。たとえば中置記法で書かれた以下の数式について考えます。

(1 + 2) - (3 + 4)

これを逆ポーランド記法に変換すると以下のようになります。

1 2 + 3 4 + -

入力される値

1 行目に逆ポーランド記法で書かれた数式の文字数 N が与えられます。 2 行目には逆ポーランド記法の数式 A の各文字が半角スペース区切りで与えられます。

N
A_1 A_2 ... A_N

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

逆ポーランド記法で計算した結果 R を出力してください。末尾には改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ N は 1 以上 10,000 未満
・ A_i は数値または演算子
・ A_i が数値の場合は 0 以上 10 未満
・ A_i が演算子の場合は + または -
・逆ポーランド記法で計算できない形式の入力は与えられない