編集履歴

回答編集履歴

バグがあることを明記

2018/01/27 13:21

投稿

スコア429

answer CHANGED Viewed

@@ -108,6 +108,8 @@
 コードが正しい保証・バグなく動く保証はまったくないです。見苦しいコードですが参考に...ならないか。
 とりあえず追記しておきます。
+さらなる追記: **バグがありました** 。例えば整数部・小数部とも省略されてしまった場合など。修正は容易ですが、今後修正していくことはできないため、鵜呑みにされることを避ける意味でも、バグがあるままにしておきます。これ以上の編集はしません。
 ```c
 #include <stdio.h>
 #include <stdlib.h>

より近い実装を追記

2018/01/27 13:21

投稿

Eki

スコア429

answer CHANGED Viewed

@@ -100,4 +100,273 @@
 ---
 このようなとき、どの部分でつまっているかを確かめるために printf デバッグが有効です。
-私はまずソースの (==A==) の部分で n, i, o を表示させてみました。終了しない原因が integer() 関数にないことや、 integer() 関数の戻り値が正しいかどうかがここで確かめられます。次に入れるとしたら (==B==) の位置です。n と i を表示させながらループを観察します。そうすると `i == -1` のときにループから戻ってこないことが分かります。きっと pow() 関数の、負値のときにバグがあるのだろうと推測することができます。
+私はまずソースの (==A==) の部分で n, i, o を表示させてみました。終了しない原因が integer() 関数にないことや、 integer() 関数の戻り値が正しいかどうかがここで確かめられます。次に入れるとしたら (==B==) の位置です。n と i を表示させながらループを観察します。そうすると `i == -1` のときにループから戻ってこないことが分かります。きっと pow() 関数の、負値のときにバグがあるのだろうと推測することができます。
+## 追記
+もっと `strtod()` の挙動に近い `str_to_d()` を書いてみました。。。
+コードが正しい保証・バグなく動く保証はまったくないです。見苦しいコードですが参考に...ならないか。
+とりあえず追記しておきます。
+```c
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <stdbool.h>
+#define WHITESPACE " \t\n\v\f\r"
+// str の中から ch を探し、インデックスを返す。
+// 見つからないときは -1
+int find_ch(char const *str, char ch);
+// ch が空白文字 WHITESPACE に含まれているかを返す
+bool is_whitespace(char ch);
+// 文字を十進整数にする
+// 範囲外の場合は -1
+int dec_to_digit(char ch);
+// 文字を十六進整数にする
+// 範囲外の場合は -1
+int hex_to_digit(char ch);
+// 符号を取得し、 nptr を進める
+// 符号は、+なら1、-なら-1
+int sign_and_eat(char const **nptr);
+// ch が大文字だったら、小文字にする
+char to_lower(char ch);
+// s と t の先頭 n 文字が (大文字小文字の区別なしで) 等しいか返す。
+bool is_same_n(char const *s, char const *t, size_t n);
+// 基数 (0x) を取得し、 nptr を進める
+int base_and_eat(char const **nptr);
+// 整数部分 (小数点 or 指数表示の e, p まで) を取得し、
+// nptr を進める。
+int integer_part_and_eat(char const **nptr, int base);
+// 小数部分 (小数点から指数表示の e, p か末尾まで) を取得し、
+// nptr を進める。
+double fraction_part_and_eat(char const **nptr, int base);
+// base の n 乗を求める。
+double pwr(double base, int n);
+// 文字列を double に変換する。
+double str_to_d(char const *nptr, char const **endptr);
+int find_ch(char const *str, char ch) {
+    for (int i = 0; str[i]; i++) {
+        if (str[i] == ch) return i;
+    }
+    return -1;
+}
+bool is_whitespace(char ch) {
+    return find_ch(WHITESPACE, ch) != -1;
+}
+int dec_to_digit(char ch) {
+    if ('0' <= ch && ch <= '9') return ch - '0';
+    return -1;
+}
+int hex_to_digit(char ch) {
+    // まず10進の範囲での変換を試みる
+    int dg = dec_to_digit(ch);
+    if (dg != -1) return dg;
+    // ダメなら文字を変換する
+    if ('A' <= ch && ch <= 'F') return 10 + (ch - 'A');
+    if ('a' <= ch && ch <= 'f') return 10 + (ch - 'a');
+    return -1;
+}
+int sign_and_eat(char const **nptr) {
+    // 符号がなければ + となるため
+    int sign = 1;
+    if (**nptr == '+') {
+        (*nptr)++;
+    } else if (**nptr == '-') {
+        sign = -1;
+        (*nptr)++;
+    }
+    return sign;
+}
+char to_lower(char ch) {
+    if ('A' <= ch && ch <= 'Z') {
+        ch = ch - 'A' + 'a';
+    }
+    return ch;
+}
+bool is_same_n(char const *s, char const *t, size_t n) {
+    for (size_t i = 0; i < n; i++) {
+        if (!s[i] || !t[i]) return false;
+        if (to_lower(s[i]) != to_lower(t[i])) return false;
+    }
+    return true;
+}
+int base_and_eat(char const **nptr) {
+    if (is_same_n(*nptr, "0x", 2)) {
+        // 0x 始まり == 16進数
+        *nptr += 2;
+        return 16;
+    }
+    return 10;
+}
+int integer_part_and_eat(char const **nptr, int base, int (*to_digit)(char)) {
+    int ans = 0;
+    int dg;
+    // 数字である限りは変換
+    for ( ; **nptr && (dg = to_digit(**nptr)) != -1; (*nptr)++) {
+        ans *= base;
+        ans += dg;
+    }
+    return ans;
+}
+double fraction_part_and_eat(char const **nptr, int base, int (*to_digit)(char)) {
+    double ans = 0;
+    int dg;
+    double pwr = 1. / base;
+    // 数字である限りは変換
+    for ( ; **nptr && (dg = to_digit(**nptr)) != -1; (*nptr)++) {
+        ans += pwr * dg;
+        pwr /= base;
+    }
+    return ans;
+}
+double pwr(double base, int n) {
+    double ans = 1;
+    if (n > 0) {
+        for (int i = 0; i < n; i++)
+            ans *= base;
+    } else if (n < 0) {
+        for (int i = 0; i < -n; i++)
+            ans /= base;
+    }
+    return ans;
+}
+double str_to_d(char const *nptr, char const **endptr) {
+#define FINISH_WHEN_ENDS() do { if (!*nptr) goto finish; } while (false)
+    // とりあえず NAN, INFINITY に対応する
+    if (is_same_n(nptr, "nan", 3)) {
+        *endptr = nptr + 3;
+        return NAN;
+    } else if (is_same_n(nptr, "infinity", 8)) {
+        *endptr = nptr + 8;
+        return INFINITY;
+    }
+    char const *oldnptr;
+    double ans = 0;
+    int sign = 1;
+    // whitespace の読み飛ばし
+    while (*nptr && is_whitespace(*nptr)) nptr++;
+    // 符号ビット
+    FINISH_WHEN_ENDS();
+    sign = sign_and_eat(&nptr);
+    // 基数
+    FINISH_WHEN_ENDS();
+    int base; base = base_and_eat(&nptr);
+    char const *expchars; expchars = base == 10 ? "eE" : "pP";
+    int (*to_digit)(char); to_digit = base == 10 ? dec_to_digit : hex_to_digit;
+    // 数字または小数点でないなら終了
+    FINISH_WHEN_ENDS();
+    if (to_digit(*nptr) == -1 && *nptr != '.') goto finish;
+    // 整数部分読み込み
+    oldnptr = nptr;
+    ans += integer_part_and_eat(&nptr, base, to_digit);
+    bool read_integer; read_integer = oldnptr != nptr;
+    // 小数点または expchars でなければ終了
+    FINISH_WHEN_ENDS();
+    bool read_dot; read_dot = false;
+    if (*nptr == '.') {
+        read_dot = true;
+        nptr++;
+    } else if (find_ch(expchars, *nptr) == -1) {
+        goto finish;
+    }
+    // 小数部分読み込み
+    oldnptr = nptr; // 変化したか確かめるため、とりあえず保存しておく。
+    ans += fraction_part_and_eat(&nptr, base, to_digit);
+    bool read_fraction; read_fraction = oldnptr != nptr;
+    // expchars でないか、 expchars であっても、
+    // 整数部省略小数であってかつ1つも進んでいない場合は終了
+    FINISH_WHEN_ENDS();
+    if (find_ch(expchars, *nptr) == -1
+            || (!read_integer && read_dot && !read_fraction)) {
+        if (!read_integer && read_dot && !read_fraction) {
+            // なぜか標準はドットから返すので、 nptr を一つ戻しておく。
+            nptr--;
+        }
+        goto finish;
+    }
+    nptr++;
+    // 符号
+    FINISH_WHEN_ENDS();
+    int exp_sign; exp_sign = sign_and_eat(&nptr);
+    // 値
+    FINISH_WHEN_ENDS();
+    int exp_num; exp_num = integer_part_and_eat(&nptr, base, to_digit);
+    // 16進数の指数表示は底が2なので。
+    double mulr; mulr = pwr(base == 10 ? 10 : 2, exp_num * exp_sign);
+    ans *= mulr;
+    if (*nptr) {
+        // なぜか標準は e を食べないので、戻す。
+        nptr--;
+    }
+finish:
+    if (endptr) *endptr = nptr;
+    return sign * ans;
+}
+int main(void)
+{
+    char const *tests[] = {
+        "134", "-542", "4234.342", "-543.435", ".5453", "-.2343", "45e2", "453.34E+4", "545.3e-2", ".e2", "4.e2",
+        "0x42", "-0x53", "0x32.42", "-0x543.53", "0x.423", "-0x.432", "0x234p2", "0x512P+4", "0x515p-2", ".p3", "2.p3",
+        "asdf", "23fab", "0xabgd", "28.eg", "4.3.3",
+        "naN", "InFiNiTy",
+        NULL,
+    };
+    double const EPS = 1e-8;
+    double f, f_std;
+    char const *endp;
+    char *endp_std;
+    for (int i = 0; tests[i] != NULL; i++) {
+        f = str_to_d(tests[i], &endp);
+        f_std = strtod(tests[i], &endp_std);
+        int num_equal = fabs(f - f_std) < EPS;
+        int rest_equal = endp == endp_std;
+        if (!num_equal || !rest_equal) {
+            printf("[%s] %f : %f (rest: %s : %s), (%d, %d)\n",
+                    tests[i], f, f_std, endp, endp_std, num_equal, rest_equal);
+        }
+    }
+    return 0;
+}
+```