ZeroJudge 解題筆記：f698. 後序運算式求值

作者：王一哲
日期：2025年6月29日


ZeroJudge 題目連結：f698. 後序運算式求值

解題想法

依序讀取算式的每個字串，如果是數字就轉成整數存入堆疊；如果是運算符號，從疊堆最上面取出兩個數字，依照運算符號種類計算兩個數字，再將計算結果存入堆疊。最後堆疊裡只會剩下一個整數，就是答案。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

ans = []
for d in input().split():
    if d not in "+-*/":
        ans.append(int(d))
    elif d == "+":
        a = ans.pop(); b = ans.pop()
        ans.append(b + a)
    elif d == "-":
        a = ans.pop(); b = ans.pop()
        ans.append(b - a)
    elif d == "*":
        a = ans.pop(); b = ans.pop()
        ans.append(b * a)
    elif d == "/":
        a = ans.pop(); b = ans.pop()
        ans.append(b // a)
print(ans[0])

C++ 程式碼

使用時間約為 2 ms，記憶體約為 348 kB，通過測試。

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    string s;          // 暫存讀取資料用的字串 s
    stringstream ss;   // 暫存資料流用的 ss
    getline(cin, s);   // 由 cin 讀取整行資料存進字串 s
    ss.clear();        // 清理 ss，如果有測資中有多行資料一定要執行
    ss << s;           // 將字串 s 的資料傳給 ss
    int a, b;          // 暫存計算資料用的變數
    stack<int> ans;    // 儲存計算結果用的堆疊
    while(ss >> s) {   // 若 ss 當中還有資料，傳給字串 s，並執行 while 迴圈中的程式碼
        if (s == "+") {         // 如果是 + 號， 從堆疊最上面取出兩筆資料存到變數 a、b，計算 b + a 並加到堆疊最上方
            a = ans.top(); ans.pop();
            b = ans.top(); ans.pop();
            ans.push(b + a);
        } else if (s == "-") {  // 如果是 - 號， 從堆疊最上面取出兩筆資料存到變數 a、b，計算 b - a 並加到堆疊最上方
            a = ans.top(); ans.pop();
            b = ans.top(); ans.pop();
            ans.push(b - a);
        }  else if (s == "*") {  // 如果是 * 號， 從堆疊最上面取出兩筆資料存到變數 a、b，計算 b * a 並加到堆疊最上方
            a = ans.top(); ans.pop();
            b = ans.top(); ans.pop();
            ans.push(b * a);
        }  else if (s == "/") {  // 如果是 / 號， 從堆疊最上面取出兩筆資料存到變數 a、b，計算 b / a 並加到堆疊最上方
            a = ans.top(); ans.pop();
            b = ans.top(); ans.pop();
            ans.push(b / a);
        } else {                 // 如果不是運算符號，將 s 轉成整數並加到堆疊最上方
            ans.push(stoi(s));
        }
    }
    cout << ans.top() << "\n";   // 堆疊中最後剩下的項目即為運算結果
    return 0;
}