972. 相等的有理数
关键词：数学
题目起源：972. 相等的有理数 - 力扣（Leetcode）
题目形容
T数学给定两个字符串 s 和 t ，每个字符串代表一个非负有理数，只有当它们示意雷同的数字时才返回 true 。字符串中能够应用括号来示意有理数的重复部分。
有理数 最多能够用三个局部来示意：整数局部\<IntegerPart>、小数非重复部分 \<NonRepeatingPart>和小数重复部分 \<(>\<RepeatingPart><)>。数字能够用以下三种办法之一来示意：
<IntegerPart>例：
0,12和123<IntegerPart><.><NonRepeatingPart>例：
0.5,1.,2.12和123.0001<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>例：
0.1(6)，1.(9)，123.00(1212)十进制开展的重复部分通常在一对圆括号内示意。例如：
1 / 6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66)输出：s = "0.(52)", t = "0.5(25)"输入：true解释：因为 "0.(52)" 代表 0.52525252...，而 "0.5(25)" 代表 0.52525252525.....，则这两个字符串示意雷同的数字。输出：s = "0.1666(6)", t = "0.166(66)"输入：true输出：s = "0.9(9)", t = "1."输入：true解释："0.9(9)" 代表 0.999999999... 永远反复，等于 1 。"1." 示意数字 1，其格局正确：(IntegerPart) = "1" 且 (NonRepeatingPart) = "" 。问题剖析
因为字符串所代表的值不会超过1e4，故可间接将字符串所示意的值求进去，而后进行比拟。
非重复部分局部容易解决，本题的关键在于如何解决重复部分。以
xxx.yyy(zzz)为例，剖析如何解决(zzz)的理论值。设有a个x，b个z，则(zzz)的理论值为0.zzz zzz zzz .../10^a，如何求0.zzz zzz zzz ...呢？0.zzz zzz zzz ...=zzz×（10^(-b)+10^(-2b)+...）=zzz/(10^b)（等比数列求和）。于是，
(zzz)的理论值为zzz/10^a/10^b。对于C和C++而言，
xxx.yyy和zzz都能够间接应用sscanf来读，故只须要确定a和b即可。代码实现
bool isRationalEqual(string s, string t) { // 误差限 const double E = 1e-12; // 将非负有理数字符串转换成数值 auto val = [&](const string &e) { double res; // 非重复部分的值 sscanf(e.c_str(), "%lf", &res); // 重复部分 if (e.back() == ')') { double r; int i = e.size() - 2, p = 1; // 找到左括号的地位 while (e[i] != '(')i--, p *= 10; // 重复部分的值 sscanf(e.c_str() + i + 1, "%lf", &r); r = r / (p - 1); // 找到小数点的地位 p = 1; while (e[--i] != '.') p *= 10; res += r /p; } return res; }; return fabs(val(s) - val(t)) < E;
工夫复杂度：O(1)