g648 - 可樂磷酸(搗蛋篇)

🔗 前往 ZeroJudge 原題

題目描述

題目要求解析一個包含數字和非數字字符的字串，並計算該字串所代表的數學表達式的值。字串中的數字之間由非數字字符分隔，非數字字符被視為運算符號。運算符號在此題中實際上只會影響數字的正負號，因為題目要求將所有乘號換成了其他字符。

解題思路

程式碼首先讀取測資筆數 n。然後，對於每個測資，讀取包含數學表達式的字串 s。程式碼使用一個迴圈來遍歷字串，將字串解析為數字和運算符號。num 數組用於存儲解析出的數字，op 數組用於存儲數字之間的運算符號（實際上只會是 1 或 -1，表示正負號）。 在解析過程中，如果遇到數字，則將其轉換為整數並存儲在 num 數組中。如果遇到非數字字符，則將其視為運算符號，並根據其是否為乘號（題目中乘號被替換成了其他字符）來確定下一個數字的正負號。 最後，程式碼遍歷 num 和 op 數組，根據運算符號計算表達式的值。如果運算符號為 1，則將後一個數字乘以前一個數字；如果運算符號為 -1，則將後一個數字乘以前一個數字的負數。

複雜度分析

• 時間複雜度: O(N)，其中 N 是字串的長度。程式碼需要遍歷字串一次來解析數字和運算符號，然後遍歷 num 和 op 數組一次來計算表達式的值。
• 空間複雜度: O(N)，其中 N 是字串的長度。num 和 op 數組的大小取決於字串中數字的數量，最壞情況下，字串中的每個字符都是一個數字，因此數組的大小為 O(N)。

程式碼

#include <iostream>
using namespace std;
long long n,num[305],op[305];
string s;
int main(){
	cin >> n;
	getline(cin,s);
	while(n--){
		getline(cin,s);
		s+='.';
		long long v=0,vs=0,f=0,fs=0,nt=0,ot=0,i=0,k=1;
		if(s[0]=='-'){
			++i;
			k=-1;
		}
		for(;i<s.size();++i){
			if(s[i]>='0'&&s[i]<='9'){
				v*=10;
				v+=s[i]-'0';
				if(fs)op[ot++]=f;
				vs=1;
				f=fs=0;
			}
			else{
				if(vs)num[nt++]=v;
				++f;
				fs=1;
				v=vs=0;	
			}
		}
		for(int i=0;i<nt-1;++i){
			if(op[i]==1){
				num[i+1]*=num[i];
			}
			else{
				num[i+1]*=(-num[i]);
			}
		}
		cout << num[nt-1]*k << "\n";
	}
}