当前位置：首页 > 洛谷 > 洛谷P1572题解析：分数计算的优化解法与代码实现

洛谷P1572题解析：分数计算的优化解法与代码实现

3个月前 (08-17)

一、题目解读

洛谷P1572题要求处理包含分数与运算符的输入表达式，计算并输出最简分数结果。题目难点在于：

1）解析混合的分数与整数表达式；

2）分数化简至最简形式；

3）处理连续加减运算。

需结合数学算法与编程逻辑，实现高效计算。

二、解题思路

1. 模块化设计：定义分数结构体（分子、分母），封装化简与加法函数，提升代码复用性。

2. GCD优化：利用辗转相除法求最大公约数，简化分数至最简形式（避免分母为负数）。

3. 输入解析：通过循环遍历字符，分离符号、分子、分母，整数视为分母为1的特殊分数。

4. 运算处理：按运算符顺序累加分数，每次加法后调用化简函数，减少重复计算。

三、解题步骤

1. 读取输入：使用getline获取整行表达式，避免空格干扰。

2. 数值分离：

○ 识别符号（+/-），记录数值正负。

○ 提取分子：连续数字拼接成整数。

○ 若遇到'/'，继续提取分母；否则默认分母为1。

3. 构建分数列表：将解析的分数存入vector，同时记录运算符。

4. 循环计算：

○ 初始化结果分数为第一个分数。

○ 遍历后续分数与运算符，根据符号执行加法或减法（转化为加法与负数）。

○ 每次运算后调用simplify()化简。

5. 输出结果：最终分数化简后输出分子与分母。

四、代码与注释

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 计算最大公约数（辗转相除法）
int gcd(int a, int b) {
    return b == 0? a : gcd(b, a % b); // 递归终止条件与迭代
}

// 分数结构体
struct Fraction {
    int numerator;   // 分子
    int denominator; // 分母

    // 化简分数：通过GCD去除公约数，确保分母为正
    void simplify() {
        int common = gcd(abs(numerator), abs(denominator));
        numerator /= common;
        denominator /= common;
        // 修正符号（分母始终为正）
        if (denominator < 0) {
            numerator *= -1;
            denominator *= -1;
        }
    }

    // 分数加法（核心运算）
    Fraction operator+(const Fraction& other) const {
        Fraction result;
        // 通分后相加：分子 = 分子1*分母2 + 分子2*分母1
        result.numerator = numerator * other.denominator + other.numerator * denominator;
        result.denominator = denominator * other.denominator;
        // 运算后立即化简
        result.simplify();
        return result;
    }
};

int main() {
    string s;
    getline(cin, s); // 输入整行表达式

    vector<Fraction> fractions; // 存储解析后的分数
    vector<char> operators;     // 存储运算符（+/-）

    // 解析输入：逐字符分离符号、分子、分母
    int i = 0;
    while (i < s.size()) {
        // 解析符号（可选）
        int sign = 1;
        if (s[i] == '-') {
            sign = -1; // 负数标记
            i++;
        } else if (s[i] == '+') {
            i++; // 跳过正号
        }

        // 解析分子（连续数字）
        int num = 0;
        while (i < s.size() && isdigit(s[i])) {
            num = num * 10 + (s[i] - '0'); // 字符转数字
            i++;
        }
        num *= sign; // 应用符号

        // 解析分母（存在'/'时）
        if (i < s.size() && s[i] == '/') {
            i++; // 跳过'/'
            int den = 0;
            while (i < s.size() && isdigit(s[i])) {
                den = den * 10 + (s[i] - '0');
                i++;
            }
            fractions.push_back({num, den}); // 存入分数
        } else {
            // 整数视为分母为1的分数
            fractions.push_back({num, 1});
        }

        // 记录运算符（后续处理）
        if (i < s.size() && (s[i] == '+' || s[i] == '-')) {
            operators.push_back(s[i]); // 存储符号
            i++; // 跳过运算符
        }
    }

    // 计算最终结果
    Fraction result = fractions[0]; // 初始化为第一个分数
    for (int j = 1; j < fractions.size(); j++) {
        // 根据运算符执行加法（减法转为加法负数）
        if (operators[j-1] == '-') {
            result = result + (-fractions[j]); // 负数分数
        } else {
            result = result + fractions[j];
        }
    }

   
     // 输出结果
    if (result.denominator == 1) {
        cout << result.numerator << endl;
    } else {
        cout << result.numerator << "/" << result.denominator << endl;
    }
    
    return 0;
}