【題解】Zerojudge j607 - 3. 先加後乘與函數

題目連結

題目大意

給定一個函式 $f(x_1, x_2, \dots, x_n)$，和一些由數字、$+$、$*$ 組成的運算式，先加後乘。請求出運算式計算的結果。

題解

因為運算的過程中要先處理加法再處理乘法，因此我們先在運算式中找到 $*$ 的位置，把運算式從這個位置切開後把兩邊的答案相乘。注意這個 $*$ 不能被括號包住。處理完乘法後就是處理加法，邏輯上大同小異。最後要處理的是 $f(x_1, x_2, \dots, x_n)$ 函數了。首先先看字串的第一項是不是 $\text{'f'}$，如果不是的話代表整個字串是一個數字，可以直接使用內建的 stoll 將這個字串轉換成數字。否則的話我們要把變數按照 $\text{','}$ 的位置切開，分別計算每個 $x_i$ 的數值，並回傳 $(最大值 - 最小值)$。其他實作的細節請參考 code。

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

long long eval(const string& s) {
	int n = s.size();
	if(n == 0) {
		return 0;
	}
	{
		// *
		int bal = 0;
		for(int i = 0; i < n; i++) {
			if(s[i] == '(') {
				bal++;
			}
			if(s[i] == ')') {
				bal--;
			}
			if(s[i] == '*' && bal == 0) {
				return eval(s.substr(0, i)) * eval(s.substr(i + 1, string::npos));
			}
		}
	}
	{
		// +
		int bal = 0;
		for(int i = 0; i < n; i++) {
			if(s[i] == '(') {
				bal++;
			}
			if(s[i] == ')') {
				bal--;
			}
			if(s[i] == '+' && bal == 0) {
				return eval(s.substr(0, i)) + eval(s.substr(i + 1, string::npos));
			}
		}
	}
	if(s[0] != 'f') {
		return stoll(s);
	}
	vector<int> cut = {1};
	int bal = 0;
	for(int i = 0; i < n; i++) {
		if(s[i] == '(') {
			bal++;
		}
		if(s[i] == ')') {
			bal--;
		}
		if(s[i] == ',' && bal == 1) {
			cut.push_back(i);
		}
	}
	cut.push_back(n - 1);
	long long mn = 1E18L;
	long long mx = -1E18L;
	for(int i = 0; i < (int) cut.size() - 1; i++) {
		long long num = eval(s.substr(cut[i] + 1, cut[i + 1] - cut[i]));
		mn = min(mn, num);
		mx = max(mx, num);
	}
	return mx - mn;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	cout << eval(s) << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge j607 - 3. 先加後乘與函數