熱門文章

2025年6月27日 星期五

ZeroJudge 解題筆記:a017. 五則運算

作者:王一哲
日期:2025年6月27日


ZeroJudge 題目連結:a017. 五則運算

解題想法


這題如果用 Python 解題,可以直接用 eval 求值。但是 Online Judge 網站通常不能使用 eval,還是要用堆疊處理算式。

Python 程式碼


由於題目要求用整數計算數值,需要先用 replace 將 / 換成 //。使用時間約為 21 ms,記憶體約為 3.3 MB,通過測試。
import sys

for line in sys.stdin:
    print(eval(line.replace("/", "//")))

將所有的程式碼寫在同一行,使用時間約為 21 ms,記憶體約為 3.3 MB,通過測試。
[print(eval(line.replace("/", "//"))) for line in __import__("sys").stdin]

以下是採用 f377. 運算式轉換,將輸入的測資轉成後序運算式,再用 f698. 後序運算式的寫法,由後序運算式求值。使用時間約為 22 ms,記憶體約為 3.4 MB,通過測試。
import sys

for line in sys.stdin:
    data = list(line.split())                # 輸入的測資儲存到串列 data
    tmp = []                                 # 暫存運算子及變數的串列
    ans = []                                 # 儲存後序運算資料的串列
    # 由輸入的測資轉成後序運算資料
    for d in data:                           # 依序從串列 data 取出字元並儲存到變數 d
        if d == ")":                         # 若 d 為 )
            while tmp[-1] != "(":            # 當 tmp 最後一項不是 ( 繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.pop()                        # 結束 while 迴圈後移除 tmp 最後一項,此時為 (
        elif d == "(":                       # 若 d 為 )
            tmp.append(d)                    # 將 d 加到 tmp 最後面
        elif d in "*/%":                     # 若 d 為 */%
            while tmp and tmp[-1] in "*/%":  # 當 tmp 之中有資料且最後一項為 */% 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        elif d in "+-":                      # 若 d 為 +=
            while tmp and tmp[-1] in "+-*/%":# 當 tmp 之中有資料且最後一項為 +-*/% 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        else:                                # 若 d 不為 ()+-*/% 即為變數
            ans.append(d)                    # 直接加到 ans 最後面 
        #print("tmp = ", tmp)
        #print("ans = ", ans)
    # 移除 tmp 最後一項並加到 ans 最後面,直到 tmp 無資料時停止
    while tmp: ans.append(tmp.pop())
    # 由處理過的後序運算資料 ans 計算結果
    func = { "+": int.__add__,       # int.__add__(a, b) = a.__add__(b) = a + b
             "-": int.__rsub__,      # int.__rsub__(a, b) = a.__rsub__(b) = b - a 
             "*": int.__mul__,       # int.__mul__(a, b) = a.__mul__(b) = a * b
             "/": int.__rfloordiv__, # int.__rfloordiv__(a, b) = a.__rfloordiv__(b) = b // a
             "%": int.__rmod__       # int.__rmod__(a, b) = a.__rmod__(b) = b % a
            }
    result = []
    for a in ans:
        if a not in "+-*/%":         # 如果 a 不是 +-*/% 則為數字
            result.append(int(a))    # 加到 result 最後面
        else:   # 如果 a 是 +-*/% 其中一個,代入字典物件 func 轉成對應的函式,取出 result 最後兩個元素並代入求值
            result.append(func[a](result.pop(), result.pop()))
    print(result[0])


C++ 程式碼


使用時間約為 3 ms,記憶體約為 344 kB,通過測試。
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    string d;                 // 暫存讀取資料用的字串 d
    stringstream ss;          // 暫存資料流用的 ss
    while(getline(cin, d)) {  // 由 cin 讀取整行資料存進字串 d
        ss.clear();           // 清理 ss,如果有測資中有多行資料一定要執行
        ss << d;              // 將字串 d 的資料傳給 ss
        stack<string> tmp;    // 暫存運算子及變數的 tmp
        vector<string> ans;   // 儲存答案的 ans
        while(ss >> d) {      // 依序從串列 ss 取出字元並儲存到變數 s
            if (d == ")") {                   // 若 d 為 )
                while(tmp.top() != "(") {     // 當 tmp 最後一項不是 ( 繼續執行
                    ans.push_back(tmp.top()); // 將 tmp 最後一項加到 ans 最後面
                    tmp.pop();                // 除除 tmp 最後一項
                }
                tmp.pop();                    // 結束 while 迴圈後移除 tmp 最後一項,此時為 (
            } else if (d == "(") {            // 若 d 為 )
                tmp.push(d);                  // 將 d 加到 tmp 最後面
            } else if (d == "*" || d == "/" || d == "%") {  // 若 d 為 */%
                while(!tmp.empty() && (tmp.top() == "*" || tmp.top() == "/" || tmp.top() == "%")) {   // 當 tmp 之中有資料且最後一項為 */% 時繼續執行
                    ans.push_back(tmp.top()); // 將 tmp 最後一項加到 ans 最後面
                    tmp.pop();                // 除除 tmp 最後一項
                }
                tmp.push(d);                  // 結束 while 迴圈後將 d 加到 tmp 最後面
            } else if (d == "+" || d == "-") {  // 若 d 為 +=
                while(!tmp.empty() && (tmp.top() == "+" || tmp.top() == "-" || tmp.top() == "*" || tmp.top() == "/" || tmp.top() == "%")) {  // 當 tmp 之中有資料且最後一項為 +-*/% 時繼續執行
                    ans.push_back(tmp.top()); // tmp 最後一項移出並加到 ans 最後面
                    tmp.pop();                // 除除 tmp 最後一項
                }
                tmp.push(d);                  // 結束 while 迴圈後將 d 加到 tmp 最後面
            } else {                          // 若 d 不為 ()+-*/% 即為變數
                ans.push_back(d);             // 直接加到 ans 最後面 
            }
        }
        // 移除 tmp 最後一項並加到 ans 最後面,直到 tmp 無資料時停止
        while(!tmp.empty()) {
            ans.push_back(tmp.top());
            tmp.pop();
        }
        // 由後序運算式 ans 求值
        int a, b;          // 暫存計算資料用的變數
        stack<int> result; // 儲存計算結果用的堆疊
        while(!ans.empty()) {                   // 若 ans 當中還有資料,執行 while 迴圈中的程式碼
            if (ans.front() == "+") {           // 如果是 + 號, 從堆疊最上面取出兩筆資料存到變數 a、b,計算 b + a 並加到堆疊最上方
                a = result.top(); result.pop();
                b = result.top(); result.pop();
                result.push(b + a);
            } else if (ans.front() == "-") {   // 如果是 - 號, 從堆疊最上面取出兩筆資料存到變數 a、b,計算 b - a 並加到堆疊最上方
                a = result.top(); result.pop();
                b = result.top(); result.pop();
                result.push(b - a);
            } else if (ans.front() == "*") {   // 如果是 * 號, 從堆疊最上面取出兩筆資料存到變數 a、b,計算 b * a 並加到堆疊最上方
                a = result.top(); result.pop();
                b = result.top(); result.pop();
                result.push(b * a);
            } else if (ans.front() == "/") {   // 如果是 / 號, 從堆疊最上面取出兩筆資料存到變數 a、b,計算 b * a 並加到堆疊最上方
                a = result.top(); result.pop();
                b = result.top(); result.pop();
                result.push(b / a);
            } else if (ans.front() == "%") {   // 如果是 % 號, 從堆疊最上面取出兩筆資料存到變數 a、b,計算 b % a 並加到堆疊最上方
                a = result.top(); result.pop();
                b = result.top(); result.pop();
                result.push(b % a);
            } else {                           // 如果不是運算符號,將 ans 最前面的資料轉成整數並加到堆疊最上方
                result.push(stoi(ans.front()));
            }
            ans.erase(ans.begin());            // 移除 ans 最前面的資料
        }
        cout << result.top() << "\n";          // 印出 result 最上方的資料,理論上此時只剩下一筆資料
    }
    return 0;
}


沒有留言:

張貼留言