# APCS實作題2023年1月第3題：先加後乘與函數 > 日期：2024年8月7日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=j607) ## 題目 ### 問題描述 給一個運算式，運算式的內容由數字、+、\*和某個函式 $f()$ 所組成，除了函式 $f()$ 以外不會有額外的括號。請將此運算式依照**先加後乘**的方式運算。 函式 $f(x_1, x_2, x_3, x_4, \dots)$ 定義為從這個不定長度的參數 $x_1, x_2, x_3, x_4, \dots$ 中的最大值扣掉最小值。例如 $f(3, 2, 6) = 6-2=4$、$f(3)=0$。 <br /> ### 輸入說明 輸入一個運算式，保證長度不超過 $500$，出現在運算式內的數字介於 0 到 200 之間，除了函式 $f()$ 之外不會出現多餘的括號，並且運算式一定合法。 - 30分：運算式只包含數字、+和\* - 70分：無其他限制 <br /> ### 輸出格式 輸出運算式的計算結果，此題運算過程和答案可能超過 $2^{31}$ 但不超過 $10^{17}$。 <br /> ### 範例輸入1 ``` 2+3*1+2+1 ``` ### 範例輸出1 ``` 20 ``` ### 範例輸入2 ``` 12+f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2))*2 ``` ### 範例輸出2 ``` 50 ``` ### 範例輸入3 ``` f(0) ``` ### 範例輸出3 ``` 0 ``` <br /><br /> ## Python 程式碼 費時最久約為 44 ms，使用記憶體最多約為 3.6 MB，通過測試。 ```python= import sys """ 自訂函式，主要的解題過程 """ def solve(s): cur = 0 # 暫存目前相加的結果 mul = [] # 最後要相乘的數值 num = "" # 目前正在讀取的數字 func = "" # f() 的內容，包含開頭的 f( cnt = 0 # 待配對的 ( 數量 if s[0] == "f": # 如果是 f，開始處理 f(n) imin = sys.maxsize # f(n) 中的最小值，預設為系統最大值 imax = -sys.maxsize # f(n) 中的最大值，預設為系統最大值加負號 cnt = 1 # 目前有一個 ( 待配對 for i in range(2, len(s)): # s 為 f(...)，從 i=2 開始向右掃過 if s[i] == "(": cnt += 1 # 遇到 ( 加 1 elif s[i] == ")": cnt -= 1 # 遇到 ) 減 1 if i == len(s)-1 or (cnt == 1 and s[i] == ","): # 如果是最後一位或是只剩一組 () 且 s[i] 是逗號 tmp = solve(num) # 遞迴，代入 num imin = min(imin, tmp) # 計算 f() 中的最小值 imax = max(imax, tmp) # 計算 f() 中的最大值 num = "" # 清空 num else: num += s[i] # 不是以上的狀況，更新 num return imax - imin # 回傳 f() 計算結果 else: # 不是 f flag = False # 是否遇到 f，預設為 False for i in range(len(s)+1): # 依序産生 0 ~ len(s)，避免少讀最後一位 if i < len(s) and (s[i] == "f" or flag): # 如果遇到 f func += s[i] # 更新 func flag = True # 更新 flag if s[i] == "(": cnt += 1 # 遇到 ( 加 1 elif s[i] == ")": cnt -= 1 # 遇到 ) 減 1 if cnt == 0: # 遞迴出口，已經沒有待配對的 ( cur += solve(func) # 遞迴，代入 func 計算數值，加到 cur func = "" # 清空 func flag = False # 重設 flag else: # 如果不是 f if i == len(s) or s[i] == "*": # 如果已讀完 s 的最後一位或是遇到 * if num: cur += int(num) # 如果 num 有內容，轉成整數加到 cur mul.append(cur) # cur 加到 mul num = "" # 清空 num cur = 0 # 重設 cur elif s[i] == "+": # 如果遇到 + if num: cur += int(num) # 如果 num 有內容，轉成整數加到 cur num = "" # 清空 num elif s[i] in "0123456789": # 如果 s[i] 是數字 num += s[i] # 更新 num # 處理完 s 的內容，最後將 mul 相乘求答案 if not mul: return 0 # 如果 mul 是空的，回傳 0 else: ans = 1 # 答案，預設值為 1 for m in mul: ans *= m # 依序取出 mul 的資料與 ans 相乘 return ans # 回傳答案 """ 結束自訂函式 """ line = input() # 讀取運算式 print(solve(line)) # 呼叫 solve，代入 line，印出答案 ``` <br /><br /> ## C++ 程式碼 費時最久約為 9 ms，使用記憶體最多約為 448 kB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <string> #include <algorithm> #include <climits> // for LLONG_MAX and LLONG_MIN typedef long long LL; // 簡化為 LL using namespace std; /* 自訂函式，主要的解題過程 */ LL solve(string s) { LL cur = 0; // 暫存目前相加的結果 int cnt = 0; // 待配對的 ( 數量 string num = "", func = ""; // 目前正在讀取的數字 num；f() 的內容，包含開頭的 f( vector<LL> mul; // 最後要相乘的數值 if (s[0] == 'f') { // 如果是 f，開始處理 f(n) LL imin = LLONG_MAX, imax = LLONG_MIN; // f(n) 中的最小值及最大值 cnt = 1; // 目前有一個 ( for(size_t i=2; i<s.size(); i++) { // s 為 f(...)，從 i=2 開始向右掃過 if (s[i] == '(') cnt++; // 遇到 ( 加 1 else if (s[i] == ')') cnt--; // 遇到 ) 減 1 if (i == s.size()-1 || (cnt == 1 && s[i] == ',')) { // 如果是最後一位或是只剩一組 () 且 s[i] 是逗號 LL tmp = solve(num); // 遞迴，代入 num imin = min(imin, tmp); // 計算 f() 中的最小值 imax = max(imax, tmp); // 計算 f() 中的最大值 num = ""; // 清空 num } else { // 不是以上的狀況，更新 num num += s[i]; } } return imax - imin; // 回傳 f() 計算結果 } else { // 不是 f bool flag = false; // 是否遇到 f，預設為 false for(size_t i=0; i<=s.size(); i++) { // 依序産生 0 ~ len(s)，避免少讀最後一位 if (i < s.size() && (s[i] == 'f' || flag)) { // 如果遇到 f func += s[i]; // 更新 func flag = true; // 更新 flag if (s[i] == '(') cnt++; // 遇到 ( 加 1 else if (s[i] == ')') { cnt--; // 遇到 ) 減 1 if (cnt == 0) { // 遞迴出口，已經沒有待配對 ( cur += solve(func); // 遞迴，代入 func 計算數值，加到 cur func = ""; // 清空 func flag = false; // 重設 flag } } } else { // 如果不是 f if (i == s.size() || s[i] == '*') { // 如果已讀完 s 的最後一位或是遇到 * if (!num.empty()) cur += stoi(num); // 如果 num 有內容，轉成整數加到 cur mul.push_back(cur); // cur 加到 mul num = ""; // 清空 num cur = 0; // 重設 cur } else if (s[i] == '+') { // 如果遇到 + if (!num.empty()) cur += stoi(num); // 如果 num 有內容，轉成整數加到 cur num = ""; // 清空 num } else if (s[i] >= '0' && s[i] <= '9') { // 如果 s[i] 是數字 num += s[i]; // 更新 num } } } // 處理完 s 的內容，最後將 mul 相乘求答案 if (mul.empty()) return 0; // 如果 mul 是空的，回傳 0 else { LL ans = 1; // 答案，預設值為 1 for(auto m : mul) ans *= m; // 依序取出 mul 的資料與 ans 相乘 return ans; // 回傳答案 } } } int main() { string line; cin >> line; // 讀取運算式 cout << solve(line) << "\n"; // 呼叫 solve，代入 line，印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`