日期: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;
}
沒有留言:
張貼留言