# ZeroJudge j607. 3. 先加後乘與函數

其實看它配分就知道要解開這題，得分成兩個階段做：

(30 分): 運算式只包含數字、+和* 
(70 分): 無其他限制

因此以下將分成兩步驟解題

### 只包含數字、+和* 30分的思路

雖然題目有規定+和\*的優先規則，但其實可以發現因為只有 **兩個運算子** 需要考慮。
所以可以維護兩個變數，一個叫做prev、一個叫做now，分別代表之前 **加總** 的運算結果和現在處理中的運算結果。為了處理優先順序還需要建一個vector叫做res
然後遇到+就直接讓 now += prev，因為+的優先級最高；遇到\*就把prev放到res裡面並將prev歸零，因為乘法左側的加總和右側的加總不能牽扯在一起。
最後將prev和res裡面的所有元素相乘就是答案了

#include <bits/stdc++.h>

#define F first
#define S second

using namespace  std;
using ll = long long;

string s;

ll caculate(int begin, int end);

int parseInt(int front, int len) {
    return stoi(s.substr(front, len));
}

ll caculate(int begin, int end) {
    ll prev = 0, now = 0;
    vector<ll> res;
    while (begin <= end) {
        if (isdigit(s[begin])) {
            int tmp = begin;
            while (tmp <= end && isdigit(s[tmp])) {
                ++tmp;
            }
            now += parseInt(begin, tmp - begin);
            prev = now;
            now = 0;
            begin = tmp;
        } else if (s[begin] == '+') {
            now += prev;
            ++begin;
        } else if (s[begin] == '*') {
            res.emplace_back(prev);
            prev = 0;
            ++begin;
        }
    }
    
    if (res.empty()) {
        return prev;
    } else {
        ll ans = prev;
        for (ll i : res) {
            ans *= i;
        }
        return ans;
    }
}

void solve() {
    cin >> s;
    cout << caculate(0, (int)s.size() - 1) << "\n";
}

int main() {
    solve();
}

## AC的思路

與上面的差別其實只在函數f的加入而已，因為f內部每個逗號隔開的運算式都可以各自視為一條獨立的運算式，所以可以用遞迴處理。

這邊我是分成兩個函式解決：caculate()和f()

其實caculate()就和上面解法中的幾乎一樣，只差在增加遇到 'f' 時的行為而已；而f()就是單純將函數f的每個參數拆開後取最大最小值相減。

比較需要注意的是，函數f有時候會有嵌套的狀況發生，這時候得注意是否取到正確的右括號，不然一但遇到嵌套f，就會直接TLE

#include <bits/stdc++.h>

#define F first
#define S second

using namespace  std;
using ll = long long;

string s;

ll caculate(int begin, int end);
ll f(int begin, int end);

ll f(int begin, int end) {
    pair<ll, ll> ext = {LLONG_MIN, LLONG_MAX};
    int ignore = 0;
    while (begin <= end) {
        int tmp = begin;
        while (tmp <= end && (s[tmp] != ',' || ignore != 0)) {
            if (s[tmp] == '(') {
                ++ignore;
            } else if (s[tmp] == ')') {
                --ignore;
            }
            ++tmp;
        }
        ll res = caculate(begin, tmp - 1);
        ext.F = max(ext.F, res);
        ext.S = min(ext.S, res);
        begin = tmp + 1;
    }
    return ext.F - ext.S;
}

int parseInt(int front, int len) {
    return stoi(s.substr(front, len));
}

ll caculate(int begin, int end) {
    ll prev = 0, now = 0;
    vector<ll> res;
    while (begin <= end) {
        if (isdigit(s[begin])) {
            int tmp = begin;
            while (tmp <= end && isdigit(s[tmp])) {
                ++tmp;
            }
            now += parseInt(begin, tmp - begin);
            prev = now;
            now = 0;
            begin = tmp;
        } else if (s[begin] == 'f') {
            int tmp = begin + 2, cnt = 1;
            while (cnt) {
                if (s[tmp] == '(') {
                    ++cnt;
                } else if (s[tmp] == ')') {
                    --cnt;
                }
                ++tmp;
            }
            now += f(begin + 2, tmp - 2);
            prev = now;
            now = 0;
            begin = tmp;
        } else if (s[begin] == '+') {
            now += prev;
            ++begin;
        } else if (s[begin] == '*') {
            res.emplace_back(prev);
            prev = 0;
            ++begin;
        }
    }
    
    if (res.empty()) {
        return prev;
    } else {
        ll ans = prev;
        for (ll i : res) {
            ans *= i;
        }
        return ans;
    }
}

void solve() {
    cin >> s;
    cout << caculate(0, (int)s.size() - 1) << "\n";
}

int main() {
    solve();
}