题解：P14088 [ICPC 2023 Seoul R] Fraction

a_gold_TomAndJerry · 2025-10-02 22:15:53 · 题解

一道不是很复杂的模拟。

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

特判方法：若栈的长度不为 1 就是括号不匹配，即没有足够的右括号进行计算。

另外，此题需要用 64 位整数，所以要开 int128。

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

AC Code：

#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;
}