0592. Fraction Addition and Subtraction ======================================= 题目信息 -------- :题号: 0592 :难度: Medium :主题: 分数表达式、加减运算、最简分数、符号处理 :原题: `LeetCode 0592 `_ :重点: 表达式由带符号分数组成、按从左到右求和、返回不可约的 numerator/denominator、零写成 0/1 题目重述 -------- 给定一个只包含分数加法和减法的合法表达式 ``expression``。每一项都写成 ``numerator/denominator``,项前可以带 ``+`` 或 ``-``;若第一项没有符号,则视为正数。 计算整个表达式的结果,并返回格式为 ``"numerator/denominator"`` 的最简分数。分母必须为正,分子和分母需要约分到互质;若结果为零,返回 ``"0/1"``。 自建示例 -------- 多项运算后仍需约分: .. code-block:: text 输入:expression = "1/2-1/3+1/6" 输出:"1/3" 解释:结果为 1/2-1/3+1/6=1/3,已经是最简分数。 结果为零: .. code-block:: text 输入:expression = "-1/4+1/4" 输出:"0/1" 解释:两项相互抵消,零按规定写成 0/1。 统一分母累加后约分 ------------------ 逐项读取可选符号、分子和分母。当前结果 ``numerator / denominator`` 加上新分数时,新的分子为 ``numerator * newDenominator + signedNumerator * denominator``,新的分母为两个分母之积;所有项处理完后用最大公约数约分。题目中的分母为正,因此结果分母也始终保持为正。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::string fractionAddition(std::string expression) { long long numerator = 0; long long denominator = 1; int i = 0; while (i < static_cast(expression.size())) { int sign = 1; if (expression[i] == '+' || expression[i] == '-') { sign = expression[i] == '-' ? -1 : 1; ++i; } long long currentNumerator = 0; while (i < static_cast(expression.size()) && std::isdigit(static_cast(expression[i]))) { currentNumerator = currentNumerator * 10 + expression[i] - '0'; ++i; } ++i; // '/' long long currentDenominator = 0; while (i < static_cast(expression.size()) && std::isdigit(static_cast(expression[i]))) { currentDenominator = currentDenominator * 10 + expression[i] - '0'; ++i; } numerator = numerator * currentDenominator + sign * currentNumerator * denominator; denominator *= currentDenominator; } long long positiveNumerator = numerator >= 0 ? numerator : -numerator; long long divisor = std::gcd(positiveNumerator, denominator); numerator /= divisor; denominator /= divisor; return std::to_string(numerator) + "/" + std::to_string(denominator); } }; 代码分析 -------- 每次合并都在同一个有理数状态上继续计算,符号只作用于当前分子;最后一次约分可同时处理正数、负数和零,零会得到 ``0/1``。设表达式包含 ``t`` 项、每项数字长度受输入限制,扫描时间为 ``O(n)``,只使用常数额外空间。