K&Rを読もう(43) 演習 4-12 itoaを再帰で

GCC

たまにはK&Rを。

演習 4-12

itoaを再帰で書け。という問題。

再帰に慣れてるはずなのに、この問題はムズィ。

int itoa_iter(int n, char s[], int i)
{
    if (n == 0) {
        s[i] = '\0';
        return i;
    } else {
        int tail = itoa_iter(n / 10, s, i + 1);
        s[tail - i] = '0' + n % 10;
        return tail;
    }
}

int itoa(int n, char s[])
{
    if (n < 0) {
        s[0] = '-';
        itoa_iter(-n, s, 1);
    } else
        itoa_iter(n, s, 0);
}

2つの部分に分けてみました。配列の長さはチェックしてないので脆弱っす。

itoa(-1234, s)の時、

  • まず、-があったら配列の先頭にマイナスを置いときます。マイナスがある場合は、1個インデックス追加。
  • ガガーっと、10で割っちゃって、0になったら、配列の最後に'\0'を置きます。
  • で、配列の最後から数を置いていければベストなんですが、残念ながら「逆順」になってしまいます。
  • 配列の先頭から値を追加したいので,0になった所で文字数を返しておきます。-1234の場合、最後のインデックス5を返します。
  • 先頭から、s[5 - 4]に1をおいて、s[5 - 3]に、2を置いて、s[5 - 2]に、3を置いて、s[5 - 1]に4を置いて"-1234"再帰完了です。


reverse無しで書けましたが、逆順になることをすっかり忘れてたので、激しく苦戦しました。やっぱK&Rは手強いです。

疑問

そういえば、itoaなんて関数あったっけ?と思って調べた。

wikipedia見たら、itoa - Wikipedia

itoa とは、標準Cライブラリの、stdlib.hにおいて宣言されている関数である。

えぇぇぇ。あったっけ!?

% man itoa
No manual entry for itoa

「な・い」

gccには入ってないので、「標準では無い思うよ」

wikipediaのウソツキ!!


追記:直ってました。

で、もうちょい

激しく破壊的に。

void itoa_iter(int n, char **s)
{
    if (n < 0) {
        **s = '-';
        *s += 1;
        itoa_iter(-n, s);
    } else if (n != 0) {
        itoa_iter(n / 10, s);
        **s = '0' + n % 10;
        *s += 1;
    }
}

void itoa(int n, char *s)
{
    itoa_iter(n, &s);
    *s = '\0';
}

ポインタポインタという手があった。これなら前から置ける。

ポインタって複雑

こう書けるみたい。

void itoa_iter(int n, char **s)
{
    if (n < 0) {
        *(*s)++ = '-';
        itoa_iter(-n, s);
    } else if (n != 0) {
        itoa_iter(n / 10, s);
        *(*s)++ = '0' + n % 10;
    }
}

イマイチ何に作用してるのかわからなくなるな・・・複雑だ。

複雑な事は抽象化

お、うまく書けた。

void push(int c, char **s)
{
    *(*s)++ = c;
}

void itoa_iter(int n, char **s)
{
    if (n != 0) {
        itoa_iter(n / 10, s);
        push('0' + n % 10, s);
    }
}

void itoa(int n, char *s)
{
    if (n < 0) {
        push('-', &s);
        n = -n;
    }
    itoa_iter(n, &s);
    push('\0', &s);
}

pushって書けばスゲーわかりやすい。

コレダ。