题解：P14088 [ICPC 2023 Seoul R] Fraction

一道不是很复杂的模拟。

因为涉及括号匹配，我们考虑使用栈来解决问题。若是左括号不会入栈，若是数字则直接入栈，若是右括号直接计算即可。并不需要考虑越界的问题，因为往前的所有数字都是计算后的结果。特殊地，括号不匹配就输出

-1

。

特判方法：若栈的长度不为

1

就是括号不匹配，即没有足够的右括号进行计算。

另外，此题需要用

64

位整数，所以要开 int128。

至于分数的实现，写个结构体就行了。

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
struct node{__int128 son,mot;};
string a[105];
int n;
stack<node> s;
inline void print(__int128 n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n % 10 + '0');
}
__int128 turn(string x){
	__int128 ans=0;
	for(int i=0;i<x.length();++i) ans=ans*10+int(x[i]-'0');
	return ans;
}
node add(node x,node y){
	node u;
	u.son=x.son*y.mot+x.mot*y.son,u.mot=x.mot*y.mot;
	__int128 gcd=__gcd(u.son,u.mot);
	return {u.son/gcd,u.mot/gcd};
}
node div(node x,node y){
	node u;
	u.son=x.son*y.mot,u.mot=x.mot*y.son;
	__int128 gcd=__gcd(u.son,u.mot);
	return {u.son/gcd,u.mot/gcd};
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i){
		if(a[i]==")"){
			node x,y,z;
			z=s.top();
			s.pop();
			y=s.top();
			s.pop();
			x=s.top();
			s.pop();
			s.push(add(x,div(y,z)));
		}else if(a[i]=="(") continue;
		else s.push({turn(a[i]),1});
	}
	if(s.size()==1){
		print(s.top().son);
		cout<<" ";
		print(s.top().mot);
	}else cout<<-1;
	return 0;
}

题解：P14088 [ICPC 2023 Seoul R] Fraction

文章操作

AC Code：

相关推荐

评论

题解：P14088 [ICPC 2023 Seoul R] Fraction