ZeroJudge F698: 後序運算式求值

平常我們在寫運算式時習慣使用「中序表示法」(Infix Notation)，也就是把運算子放在兩個運算元中間，例如「3 + 4」。1924 年一位波蘭的邏輯學家 Jan Łukasiewicz 發明了「前序表示法」(Prefix Notation)，它卻是把運算子放在運算元的前面，例如 「+ 3 4」。

儘管前序表示法並不符合人類的閱讀習慣，它的好處是不需要用到任何括號就可以清楚地指定運算的順序。比如說，在我們慣用的中序表示法裡：

1 + 2 × 3 = 7

因為會先算乘除再算加減。如果你要先算加減的話就得使用括號：

(1 + 2) × 3 = 9

但是如果使用前序表示法就不需要括號了：

+ 1 × 2 3 = 7
× + 1 2 3 = 9

前序表示法也稱作「波蘭表示法」(PN, Polish Notation)。

後來當電腦發明了以後，工程師們發現前序表示法在求值時耗用較多的記憶體，於是在 1954 年 Arthur Walter Burks 提出了「後序表示法」，把運算子放在運算元的後面，一樣不需要括號就可以指定不同的運算順序：

1 2 3 × + = 7
1 2 + 3 × = 9

但是它只要使用「堆疊」就可以很簡單的完成求值動作。

後序表示法使用在 HP 於 1970 及 1980 年代所推出的所有電子計算器，甚至於 2020 年代的某些機型仍在使用。也用在一些堆疊導向的程式語言，例如 Forth。以下是一個後序計算機，你可以玩玩看：http://www.alcula.com/calculators/rpn/。

後序表示法也稱作「逆波蘭表示法」(RPN, Reverse Polish Notation) 或「波蘭後序表示法」(Polish Postfix Notation)。

現在，請你幫一個後序表示法運算式求值。

範例測資

解題思路

使用 Stack 來存資料，並且用字串的方式 EOF 收資料。當收到數字時就將數字 push 到 Stack 中。當收到的不是數字時，就將 Stack 的兩個 top 拿出來做計算，需要記得要 pop，並且第一個 top 是 加數 (或減數、乘數、除數)。運算完之後將結果 push 回 stack 中。最後應該 Stack 中只會剩下一個數字，將其輸出。

範例程式碼－ZeroJudge F698: 後序運算式求值

#include <iostream>
#include <stack>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string str;
    stack<string>sb;
    while (cin >> str) {
        if (str == "+" || str == "-" || str == "*" || str == "/") {
            const int b = stoi(sb.top());
            sb.pop();
            const int a = stoi(sb.top());
            sb.pop();
            if (str == "+") sb.push(to_string(a + b));
            else if (str == "-") sb.push(to_string(a - b));
            else if (str == "*") sb.push(to_string(a * b));
            else if (str == "/") sb.push(to_string(a / b));
        }
        else {
            sb.push(str);
        }
    }
    cout << sb.top() << "\n";
}

//ZeroJudge F698
//Dr. SeanXD