C++で2つの有理数が等しいかどうかを判定する方法

問題の概要

2つの文字列 S と T があるとします。それぞれ正の有理数を表しており、両者が同じ数値を表しているかどうかを判定するのが課題です。文字列では、有理数の循環小数部分（繰り返し部分）を括弧「( )」で示すことができます。

ご存知のとおり、有理数は最大で3つの部分、すなわち「整数部分」「非循環部分」「循環部分」を使って表現できます。数値の表記は、次の3つの形式のいずれかになります。

• 整数部分のみ（例：0、12、123）
• 整数部分.非循環部分（例：0.5、1.0、2.12、2.0001）
• 整数部分.非循環部分(循環部分)（例：0.1(6)、0.9(9)、0.00(1212)）

たとえば、0.1(6)、0.1666(6)、0.166(66) は、いずれも 1/6 を正しく表す表記です。

したがって、入力が S = "0.(52)"、T = "0.5(25)" の場合、どちらも 0.525252... を表すため、出力は True になります。

解き方のアプローチ

この問題は、循環節を実際に展開して数値として比較するというシンプルな方針で解けます。手順は以下の通りです。

• 文字列 S を受け取る関数 f() を定義します。
• S 内の '(' の位置 i を検索します。
• '(' が見つかった場合は、次のように処理します。
  • base ← S の先頭から '(' の直前までの部分文字列（整数部＋非循環部）
  • rep ← '(' の後ろにある循環部分の文字列
  • j を 0 から 19 まで動かしながら、base に rep を 20 回連結し、循環節を十分な長さまで展開します。
• base を double 型の実数値に変換して返します。'(' が含まれない場合は、S をそのまま実数値に変換して返します。
• メイン処理では、f(S) と f(T) が一致すれば true を返します。

循環節を 20 回程度繰り返せば、double 型の精度で比較できる十分な桁数になるため、誤差による誤判定をほぼ防ぐことができます。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool isRationalEqual(string S, string T){
        return f(S) == f(T);
    }
    double f(string S){
        auto i = S.find("(");
        if (i != string::npos) {
            string base = S.substr(0, i);
            string rep = S.substr(i + 1, S.length() - i - 2);
            for (int j = 0; j < 20; ++j)
            base += rep;
            return stod(base);
        }
        return stod(S);
    }
};
main(){
    Solution ob;
    cout << (ob.isRationalEqual("0.(52)", "0.5(25)"));
}

入力

"0.(52)", "0.5(25)"

出力

1

"0.(52)" は 0.525252… を表し、"0.5(25)" も同じく 0.525252… を表します。そのため両者は等しいと判定され、結果として 1（true）が出力されます。