先加後乘與函數題解｜APCS 2023 年 1 月中高級第 3 題

前置知識

這題的核心推導（三層結構、一層呼叫一層）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：

遞迴：NTUCPC Guide〈遞迴〉；吳邦一《AP325》第 1 章（Python 版第 1 章）——要帶走的是「假裝函式已經寫好了，直接呼叫它處理小一號的問題」。
逐字元讀字串：s[i] 與 isdigit——連續的數字字元要自己拼成一個數。
用堆疊算運算式的另一條路：《AP325》第 3 章習題 Q-3-3 加減乘除（Python 版第 3 章）。這題有函數和不固定個數的參數，用遞迴寫比堆疊直接得多，下面只講遞迴。

簡潔題意

一行運算式，由 \(0 \sim 200\) 的整數、+、* 和函數 f(...) 組成，長度不超過 \(500\)。規則是先加後乘：+ 比 * 優先。f 可以有任意多個參數（至少一個），每個參數本身又是一個運算式，值是「參數的最大值減最小值」。除了 f 的括號外沒有其他括號。求運算式的值（不超過 \(10^{17}\)）。

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

子題組 1（\(30\) 分）：只有數字、+ 和 *。
子題組 2（\(70\) 分）：無額外限制。

先拿下 30 分：用 `*` 把字串切成幾段

「先加後乘」換個說法：* 是最後才做的，所以整個運算式就是「用 * 隔開的幾段，每段只有加法」——範例 1 的 2+3*1+2+1 是 2+3 和 1+2+1 兩段，\((2 + 3) \times (1 + 2 + 1) = 20\)。由左到右掃一次就算得完：數字字元拼進 number，遇到 + 或 * 表示一個數字讀完了、加進目前這段的和 part；遇到 * 還要把 part 乘進答案、歸零。最後一段後面沒有 *，先在字串尾巴補一個 *，就不用特別處理。

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

int main() {
    string s;
    cin >> s;
    s += '*';                        // 尾巴補一個 *，讓最後一段也會被結算
    long long answer = 1;            // 各段的乘積
    long long part = 0;              // 目前這一段的和
    long long number = 0;            // 正在讀的數字
    for (int i = 0; i < (int)s.size(); i++) {
        if (isdigit(s[i])) {
            number = number * 10 + (s[i] - '0');
        } else {                     // 遇到 + 或 *：一個數字讀完了
            part += number;
            number = 0;
            if (s[i] == '*') {       // 一個加法段結束：乘進答案
                answer *= part;
                part = 0;
            }
        }
    }
    cout << answer << endl;
    return 0;
}

答案要用 long long：題目說結果可能到 \(10^{17}\)，int 只到 \(2147483647\)（估算方法見語法書 2.9）。只有數字和加乘的六筆測資就是 \(30\) 分，穩穩到手；有 f 的測資這份程式會把 f( 當成分隔符號亂算，範例 2、3 會 WA 是正常的。

從 30 分到 100 分：三層結構、一層呼叫一層

加進 f 之後，「用 * 切段」的想法還是對的，只是段裡面可能藏著 f(...)，而 f 的參數本身又是一個完整的運算式——裡面又能切段。把這個結構寫清楚就是三層（圖 1）：

運算式＝加法段 * 加法段 * ……
加法段＝基本項 + 基本項 + ……
基本項＝一個數字，或 f( 運算式 , 運算式 , …… )

圖 1：運算式／加法段／基本項三層，f 的參數又回到運算式那一層；範例 1 切成 2+3 與 1+2+1 兩段

三層各寫成一個函式，每個函式都「從目前位置 pos 開始讀、讀完自己負責的那一塊就停、回傳它的值」：

expression()：先讀一個加法段，只要下一個字元是 * 就再讀一個加法段乘上去。
addition()：先讀一個基本項，只要下一個字元是 + 就再讀一個基本項加上去。
item()：看到數字就把連續的數字字元拼成一個數；看到 f 就跳過 f(，呼叫 expression() 讀第一個參數，之後每看到一個 , 就再讀一個參數，最後跳過 )。參數的最大、最小值從第一個參數的值開始擂台——參數是算出來的，可以遠大於 \(200\)，初值寫死某個數一定出事。

遇到 f 時 item() 呼叫 expression()，expression() 又會一路呼叫到 item()：這就是遞迴，巢狀多深都能處理。字串裡沒有空白、保證合法，所以不用檢查格式。

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

string s;
int pos = 0;                     // 目前讀到字串的哪個位置

long long expression();

long long item() {               // 基本項：一個數字，或 f( 運算式 , 運算式 , ... )
    if (s[pos] == 'f') {
        pos += 2;                            // 跳過 "f("
        long long v = expression();          // 第一個參數
        long long mx = v, mn = v;            // 最大、最小值的初值用第一個參數
        while (s[pos] == ',') {
            pos++;                           // 跳過 ','
            v = expression();
            mx = max(mx, v);
            mn = min(mn, v);
        }
        pos++;                               // 跳過 ')'
        return mx - mn;
    }
    long long v = 0;
    while (pos < (int)s.size() && isdigit(s[pos])) {   // 連續的數字字元組成一個數
        v = v * 10 + (s[pos] - '0');
        pos++;
    }
    return v;
}

long long addition() {           // 加法段：基本項 + 基本項 + ...
    long long v = item();
    while (pos < (int)s.size() && s[pos] == '+') {
        pos++;
        v += item();
    }
    return v;
}

long long expression() {         // 運算式：加法段 * 加法段 * ...
    long long v = addition();
    while (pos < (int)s.size() && s[pos] == '*') {
        pos++;
        v *= addition();
    }
    return v;
}

int main() {
    cin >> s;
    cout << expression() << endl;
    return 0;
}

expression() 在 item() 後面才定義，所以最前面要先宣告一行 long long expression();，item() 才呼叫得到它。每個字元只被讀一次，\(O(|s|)\)；f 每多一層巢狀至少多占 f( 和 ) 三個字元，長度 \(500\) 的字串最多一百多層，遞迴很安全。

測過再交：範例的 `f` 參數都很小

三個範例蓋到了先加後乘、巢狀的 f、單一參數的 f(0)。沒蓋到的：某一段的和是 \(0\) 讓整個乘積歸零、三個以上的參數而且最大最小都不在頭尾、參數算出來比 \(200\) 大很多（驗最大最小值的初值）、連續好幾層只有一個參數的 f、以及接近 \(10^{17}\) 的大答案。

輸入	正確輸出	這一筆在測什麼
`0*5+3`	`0`	第一段是 \(0\)，乘積就是 \(0\)（先乘後加會印 `3`）
`f(2,5,1,4,3)`	`4`	五個參數，最大最小都在中間：\(5 - 1\)
`f(200200200,200200200*200)`	`1592000000`	參數是算出來的，兩個都遠大於 \(200\)：最大最小值的初值一定要用第一個參數
`f(f(f(1)))`	`0`	連續三層單一參數：每一層都是 \(x - x = 0\)
`200200200200200200200`	`12800000000000000`	\(1.28 \times 10^{16}\)，`int` 裝不下
`f(2+34,1)2+1`	`57`	`f` 裡面也是先加後乘：\(f(20, 1) = 19\)，再 \(19 \times (2 + 1)\)

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

常犯錯誤

照一般的先乘後加：範例 1 印 8、範例 2 印 36。
f 的最小值初值寫死（mn = 200 或 mn = 1000000）：三個範例都過——參數算出來比初值大時就錯，自測表第 3 列印 1599999800（初值 \(200\)）或 1599000000（初值 \(10^6\)）。
f 只拿最大值、忘了減最小值：範例 2 印 184；自測表第 2 列印 5。
f 只比第一個和最後一個參數：三個範例都過，計分測資掛 \(2\) 筆；自測表第 2 列印 1。
讀 f 的參數時只讀一個數字，沒有呼叫完整的 expression()：範例 2 印 23。
讀完最後一個參數忘了跳過 )：範例 2 印 22；自測表第 6 列印 19。
用 int：三個範例都過，計分測資掛 \(1\) 筆；自測表第 5 列印 1025507328。

先加後乘與函數 題解｜APCS 2023 年 1 月中高級 第 3 題