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