# APCS實作題2019年2月第3題：函數運算式求值
> 日期：2023年10月24日
> 作者：王一哲
> 題目來源：108年2月實作題第3題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f640)
<br />
## 題目
### 問題描述
有三個函數：
$$
f(x) = 2x - 3 \\
g(x, y) = 2x + y - 7\\
h(x, y, z) = 3x - 2y + z
$$
另有一個由這三個函數所組成的運算式，依序給你其中的函數名稱及參數，請求出這個運算式的值。例如：
```
h f 5 g 3 4 3
```
代表
$$
h(f(5), g(3, 4), 3) = h(7, 3, 3) = 18
$$
<br />
### 輸入說明
輸入只有一行，含有運算式中所有的函數名稱及參數值，兩兩以一個空白隔開。函數名稱為 f、g、h 其中一個字母，參數值則為一個介於 $-1000$ 及 $1000$ 的整數。
<br />
### 輸出說明
輸出運算式的值。運算過程及結果的整數值其絕對值均不大於 $10^9$。
<br />
### 範例一：輸入
```
f f f 2
```
### 範例一：正確輸出
```
-5
```
<br />
### 範例二：輸入
```
h f 5 g 3 4 3
```
### 範例二：正確輸出
```
18
```
<br />
## Python 程式碼
### 方法1，使用堆疊
```python=
ss = input().split() # 由標準輸入讀取資料，存入串列 ss
nums = [] # 儲存數值及運算結果的串列
while ss: # 當 ss 還有元素時繼續執行
s = ss.pop() # 取出 ss 最後一個元素存入字串 s
if s == 'f': # 如果 s 為 'f'
x = nums.pop() # 取出 nums 最後一個元素存入變數 x
nums.append(2*x - 3) # 計算 f(x) 並加到 nums 最後面
elif s == 'g': # 如果 s 為 'g'
x = nums.pop() # 取出 nums 最後一個元素存入變數 x
y = nums.pop() # 取出 nums 最後一個元素存入變數 y
nums.append(2*x + y - 7) # 計算 g(x, y) 並加到 nums 最後面
elif s == 'h': # 如果 s 為 'h'
x = nums.pop() # 取出 nums 最後一個元素存入變數 x
y = nums.pop() # 取出 nums 最後一個元素存入變數 y
z = nums.pop() # 取出 nums 最後一個元素存入變數 z
nums.append(3*x - 2*y + z) # 計算 h(x, y, z) 並加到 nums 最後面
else: # 如果 s 不是 'f', 'g', 'h'
nums.append(int(s)) # 將 s 轉成整數並加到 nums 最後面
print(nums[0]) # 最後 nums 只剩下一個元素，就是運算結果
```
<br />
以範例二說明 while 迴圈運作流程：
1. 取出 ss 最後一個元素 3，轉成整數加到 nums 最後面，此時 ss 內容為 ['h', 'f', '5', 'g', '3', '4']，nums 內容為 [3]。
2. 取出 ss 最後一個元素 4，轉成整數加到 nums 最後面，此時 ss 內容為 ['h', 'f', '5', 'g', '3']，nums 內容為 [3, 4]。
3. 取出 ss 最後一個元素 3，轉成整數加到 nums 最後面，此時 ss 內容為 ['h', 'f', '5', 'g']，nums 內容為 [3, 4, 3]。
4. 取出 ss 最後一個元素 g，取出 nums 最後面兩個元素，$x = 3, y = 4$，計算 $g(3, 4) = 2 \times 3 + 4 - 7 = 3$，再將 3 加到 nums 最後面，此時 ss 內容為 ['h', 'f', '5']，nums 內容為 [3, 3]。
5. 取出 ss 最後一個元素 ，轉成整數加到 nums 最後面，此時 ss 內容為 ['h', 'f']，nums 內容為 [3, 3, 5]。
6. 取出 ss 最後一個元素 f，取出 nums 最後面一個元素，$x = 5$，計算 $f(5) = 2 \times 5 －3 = 7$，再將 7 加到 nums 最後面，此時 ss 內容為 ['h']，nums 內容為 [3, 3, 7]。
7. 取出 ss 最後一個元素 h，取出 nums 最後面三個元素，$x = 7, y = 3, z = 3$，計算 $h(7, 3, 3) = 3 \times 7 - 2 \times 3 + 3 = 18$，再將 3 加到 nums 最後面，此時 ss 已經沒有任何元素，nums 內容為 [18]。
於 ZeroJudge 測試結果，花費時間約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。
<br /><br />
### 方法2，使用函式遞迴
```python=
ss = input().split() # 由標準輸入讀取資料，存入串列 ss
def sol(): # 自訂函式，解題用的主要部分 sol
s = ss.pop(0) # 取出 ss 最後一個元素存入字串 s
if s == 'f': return f() # 如果 s 為 'f' 呼叫 f()
elif s == 'g': return g() # 如果 s 為 'g' 呼叫 g()
elif s == 'h': return h() # 如果 s 為 'h' 呼叫 h()
else: return int(s) # 如果 s 不是 'f', 'g', 'h'，將 s 轉成整數
def f(): # 自訂函式 f()
x = sol() # 呼叫 sol()，找出要代入的 x 數值
return 2*x - 3 # 回傳 2*x -3 計算結果
def g(): # 自訂函式 g()
x = sol() # 呼叫 sol()，找出要代入的 x 數值
y = sol() # 呼叫 sol()，找出要代入的 y 數值
return 2*x + y - 7 # 回傳 2*x + y - 7 計算結果
def h(): # 自訂函式 h()
x = sol() # 呼叫 sol()，找出要代入的 x 數值
y = sol() # 呼叫 sol()，找出要代入的 y 數值
z = sol() # 呼叫 sol()，找出要代入的 z 數值
return 3*x - 2*y + z # 回傳 3*x - 2*y + z 計算結果
ans = sol() # 呼叫 sol() 計算答案
print(ans) # 印出答案
```
<br />
這個寫法是從國立中正大學資訊工程學系吳邦一教授編寫的 APCS 講義《[AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)》找到的，我只有稍微修改一下，將 sol() 中讀取資料的部分改成 s = ss.pop(0)，刪掉記錄索引值用的全域變數 index。以範例二說明呼叫 sol() 的運作流程：
1. 取出 ss 最前方的元素 'h'，呼叫 h()，進到 h()。
2. 於 h() 中呼叫 sol() 計算 x, y, z
3. 取出 ss 最前方的元素 'f'，呼叫 h()，進到 f()。
4. 於 f() 中呼叫 sol() 計算 x
5. 取出 ss 最前方的元素 '5'，轉成整數再回傳給 x。
6. 回到步驟4的 f()，計算 $f(5) = 2 \times 5 - 3 ＝ 7$，回到步驟2的 h()，$x = 7$。
7. 回到步驟2的 h()，於 h() 中呼叫 sol() 計算 y
8. 取出 ss 最前方的元素 'g'，呼叫 g()，進到 g()
9. 於 g() 中呼叫 sol() 計算 x, y
10. 取出 ss 最前方的元素 '3'，轉成整數再回傳給 x
11. 取出 ss 最前方的元素 '4'，轉成整數再回傳給 y
12. 回到步驟9的 g()，計算 $g(3, 4) = 2 \times 3 + 4 - 7 = 3$，回到步驟2的 h()，$y = 3$。
13. 回到步驟2的 h()，呼叫 sol() 計算 z
14. 取出 ss 最前方的元素 '3'，轉成整數再回傳給 z。
15. 回到步驟2的 h()，計算 $h(7, 3, 3) = 3 \times 7 - 2 \times 3 + 3 ＝ 18$。
於 ZeroJudge 測試結果，花費時間約為 18 ms，使用記憶體最多約為 3.3 MB，通過測試。
<br /><br />
## C++ 程式碼
### 方法1，使用堆疊
```cpp=
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
string s; // 暫存資料的字串
stack<string> ss; // 儲存由標準輸入讀取資料用的堆疊
stack<int> nums; // 儲存數值及運算結果的堆疊
while(cin >> s) ss.push(s); // 由標準輸入讀取資料，先存入 s，再將 s 加到 ss 最上面
while(!ss.empty()) { // 當 ss 還有資料時繼續執行
s = ss.top(); ss.pop(); // 取出 ss 最上方的資料存入字串 s
if (s == "f") { // 如果 s 為 "f"
int x = nums.top(); nums.pop(); // 取出 nums 最上方的資料存入變數 x
nums.push(2*x - 3); // 計算 f(x) 並加到 nums 最上方
} else if (s == "g") { // 如果 s 為 "g"
int x = nums.top(); nums.pop(); // 取出 nums 最上方的資料存入變數 x
int y = nums.top(); nums.pop(); // 取出 nums 最上方的資料存入變數 y
nums.push(2*x + y - 7); // 計算 g(x, y) 並加到 nums 最上方
} else if (s == "h") { // 如果 s 為 "h"
int x = nums.top(); nums.pop(); // 取出 nums 最上方的資料存入變數 x
int y = nums.top(); nums.pop(); // 取出 nums 最上方的資料存入變數 y
int z = nums.top(); nums.pop(); // 取出 nums 最上方的資料存入變數 z
nums.push(3*x - 2*y + z); // 計算 h(x, y, z) 並加到 nums 最上方
} else { // 如果 s 不是 "f", "g", "h"
nums.push(stoi(s)); // 將 s 轉成整數並加到 nums 最上方
}
}
cout << nums.top() << endl; // 最後 nums 只剩下一個元素，就是運算結果
return 0;
}
```
<br />
由 Python 程式碼方法1改寫而成，於 ZeroJudge 測試結果，花費時間約為 3 ms，使用記憶體最多約為 352 kB，通過測試。
<br /><br />
### 方法2，使用函式遞迴
```cpp=
#include <iostream>
#include <string>
using namespace std;
int sol() { // 自訂函式，解題用的主要部分 sol
int x, y, z; // 整數變數 x, y, z
string s; cin >> s; // 由標準輸入讀取資料存入字串 s
if (s == "f") { // 如果 s 為 "f"
x = sol(); // 呼叫 sol()，找出要代入的 x 數值
return 2*x - 3; // 回傳 2*x -3 計算結果
} else if (s == "g") { // 如果 s 為 "g"
x = sol(); // 呼叫 sol()，找出要代入的 x 數值
y = sol(); // 呼叫 sol()，找出要代入的 y 數值
return 2*x + y - 7; // 回傳 2*x + y - 7 計算結果
} else if (s == "h") { // 如果 s 為 "h"
x = sol(); // 呼叫 sol()，找出要代入的 x 數值
y = sol(); // 呼叫 sol()，找出要代入的 y 數值
z = sol(); // 呼叫 sol()，找出要代入的 z 數值
return 3*x - 2*y + z; // 回傳 3*x - 2*y + z 計算結果
} else { // 如果 s 不是 "f", "g", "h"
return stoi(s); // 將 s 轉成整數並回傳
}
}
int main() {
cout << sol() << endl;
return 0;
}
```
<br />
這個寫法是從國立中正大學資訊工程學系吳邦一教授編寫的 APCS 講義《[AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)》找到的，我只有稍微修改一下，改成引用 string 函式庫，用 string 儲存讀取的資料，用 stoi 將字串轉成整數。於 ZeroJudge 測試結果，花費時間約為 3 ms，使用記憶體最多約為 328 kB，通過測試。
<br /><br />
---
###### tags:`APCS`、`C++`、`Python`
Sign in with Wallet
Connect another wallet