函數運算式求值 題解｜APCS 2019 年 2 月中高級 第 3 題

前置知識

這題的核心（前序記法怎麼「讀一個 token 就決定接下來要再讀幾個運算式」）下面會從頭講；要先會的是：

• 遞迴：NTUCPC Guide〈遞迴〉——要帶走的是「一個函式在自己裡面再呼叫自己，每一層有自己的區域變數」。吳邦一《AP325》第 1 章的例題 P-1-1 合成函數（1） 和本題幾乎是同一題（只差函數的定義），習題 Q-1-2 就是本題（教材 PDF 第 29～31 頁；Python 版第 1 章）。
• 字串轉整數：stoll("-1000") 自己會處理負號和多位數。
• 堆疊（最後的「另一種做法」會用到）：NTUCPC Guide〈Stack、Queue 與 Deque〉。

簡潔題意

輸入一行 token（以一個空白隔開），是三個函數 \(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) = 18\)。輸出整個運算式的值（token 數 \(1\) 到 \(500\)，每個整數在 \(-1000\) 到 \(1000\) 之間，運算過程中每個函數值和最後答案的絕對值都不超過 \(10^9\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(10\) 分）：只會出現 f，整數都在 \(0\) 到 \(9\)。
• 子題組 2（\(40\) 分）：整數都在 \(0\) 到 \(9\)。
• 子題組 3（\(50\) 分）：無額外限制。

先拿下子題組 1：數有幾個 f

只有 f 的運算式長得像 f f f 2：一串 f 包著一個整數。從裡往外一層一層套 \(f\) 就好——數有幾個 f、把最後那個整數讀出來，套那麼多次 \(2x - 3\)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string token;
    int countF = 0;
    long long value = 0;
    while (cin >> token) {               // 一個一個 token 讀到沒有為止
        if (token == "f") countF++;      // 數有幾層 f
        else value = stoll(token);       // 最後一個 token 是那個整數
    }
    for (int i = 0; i < countF; i++) value = 2 * value - 3;   // 由內往外套 countF 次
    cout << value << endl;
    return 0;
}

範例 1 f f f 2：\(2 \to 1 \to -1 \to -5\)。這個版本遇到 g、h 會把它當整數轉換而直接當掉（範例 2 就會），子題組 1 的 \(10\) 分穩穩到手。

從 10 分到 100 分：讀到函數名稱就遞迴讀它的參數

前序記法的好處是不用括號也能唯一決定結構：讀到 f 就知道後面緊接著恰好一個運算式是它的參數；讀到 g 後面緊接著兩個、h 三個；讀到整數就是一個完整的運算式。「讀入下一個完整的運算式並回傳它的值」寫成函式 eval()：

• 讀一個 token。
• 是 f：呼叫一次 eval() 拿到 \(x\)，回傳 \(2x - 3\)。
• 是 g：呼叫兩次拿到 \(x\)、\(y\)，回傳 \(2x + y - 7\)。
• 是 h：呼叫三次拿到 \(x\)、\(y\)、\(z\)，回傳 \(3x - 2y + z\)。
• 都不是：它就是一個整數，stoll 之後回傳。

每次呼叫 eval() 都會把「屬於這個運算式的 token」剛好讀完，所以下一次呼叫自然從下一個參數開始讀——不用自己記位置。範例 2 的呼叫過程見圖 1。

#include <bits/stdc++.h>
using namespace std;

long long eval() {                   // 讀入「下一個完整的運算式」，回傳它的值
    string token;
    cin >> token;
    if (token == "f") {
        long long x = eval();        // f 後面接一個運算式
        return 2 * x - 3;
    }
    if (token == "g") {
        long long x = eval();        // g 後面接兩個運算式，先讀到的是 x
        long long y = eval();
        return 2 * x + y - 7;
    }
    if (token == "h") {
        long long x = eval();        // h 後面接三個運算式
        long long y = eval();
        long long z = eval();
        return 3 * x - 2 * y + z;
    }
    return stoll(token);             // 不是函數名稱，就是一個整數（stoll 自己會處理負號）
}

int main() {
    cout << eval() << endl;
    return 0;
}

幾個細節：

• token 用 string 讀再用 stoll 轉，負號和多位數（-1000）自然都對；子題組 2 和 3 的差別只在整數的範圍，這份程式一次拿下 \(90\) 分。
• 題目保證每個函數值不超過 \(10^9\)，但算 \(h\) 的時候會先算 \(3x\)，\(x\) 接近 \(10^9\) 時 \(3x\) 可到 \(3 \times 10^9\)，超過 int 的 \(2147483647\)（估算方法見語法書 2.9）——中間值一律用 long long。
• 每個 token 剛好被讀一次，\(O(T)\)；遞迴最深 \(500\) 層（f f f ... 3），完全不是問題。

測過再交：範例沒有負數和多位數

範例 1 是一串 f、範例 2 三種函數各一個，但整數全是一位數、沒有負數，而且 h 的後兩個參數剛好都是 \(3\)——把 \(y\)、\(z\) 拿反也看不出來。補的是：單一個整數、負的多位數、g 裡面包 h、h 三個參數都不一樣、最深的遞迴。

五筆都親眼看過正確，這題就穩了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<string> tokens;
    string token;
    while (cin >> token) tokens.push_back(token);
    vector<long long> values;                    // 當堆疊用：最後面是最上面
    for (int i = (int)tokens.size() - 1; i >= 0; i--) {   // 從最後一個 token 往前看
        if (tokens[i] == "f") {
            long long x = values.back();         // 最上面的就是它的參數
            values.pop_back();
            values.push_back(2 * x - 3);
        } else if (tokens[i] == "g") {
            long long x = values.back();         // 先拿到的是 x（它離 g 比較近）
            values.pop_back();
            long long y = values.back();
            values.pop_back();
            values.push_back(2 * x + y - 7);
        } else if (tokens[i] == "h") {
            long long x = values.back();
            values.pop_back();
            long long y = values.back();
            values.pop_back();
            long long z = values.back();
            values.pop_back();
            values.push_back(3 * x - 2 * y + z);
        } else {
            values.push_back(stoll(tokens[i]));  // 整數：先放著，等函數來拿
        }
    }
    cout << values.back() << endl;               // 最後堆疊裡只剩整個運算式的值
    return 0;
}