C言語で文字列の単語を抽出する【strtok, 状態遷移、自作mystrtok】

489, 2022-06-08

目次

C言語で文字列の単語を抽出する

C言語で文字列内の単語を抽出したい場合があります。
そういう時は文字列をパース(解析)して単語を抜き出します。

C言語だとstrtok()などの標準ライブラリがありますが、これを使うと単語を抽出できます。
他には状態遷移を使ったパースや、strtok()を改良した自作mystrtok()を使う方法もあります。

この記事ではこれらの方法について解説します。

関連記事


strtokを使う方法

strtok()string.hをインクルードすると使える関数です。
この関数は指定の文字列を指定の区切り文字で分割します。
第1引数の文字列を破壊的にパースするので、解析対象の文字列を破壊したくない場合は注意が必要です。
それからこの関数は内部でstaticな変数を使っています。
そのため非スレッドセーフです。マルチスレッドなプログラムで使う場合は注意が必要です。

#include <stdio.h>
#include <string.h>

int main(void) {
    char str[] = "cat dog bird";
    char *tok;

    tok = strtok(str, " ");  // 半角スペース区切りでパース
    for (; tok; ) {
        puts(tok);
        tok = strtok(NULL, " ");
    }

    return 0;
}

上記のコードを実行すると↓の結果になります。

cat
dog
bird

strtok()はけっこう特殊なインターフェースを持っています。
これはstrtok()staticな変数を内部で使っていることによる結果です。
この関数は非スレッドセーフでマルチスレッドでは使えないので並行処理を行うような高度なプログラムではあまり使用されません。

ちなみに第2引数の区切り文字は複数指定することができます。

strtok(str, " ,:");  // ' 'と','と':'をパース

区切り文字を変更する場合はstrtok(NULL, " ")の方も変更するのを忘れないようにしてください。

状態遷移でパースする方法

状態遷移とは処理に状態を持たせてその状態を変化させながら解析していく手法です。
この状態遷移は文字列のパースにも応用できます。
文字列を半角スペース区切りでパースする場合は↓のようにします。

#include <stdio.h>
#include <string.h>

int main(void) {
    const char *str = "cat dog  bird";
    int m = 0;

    for (const char *p = str; *p; p += 1) {
        switch (m) {
        case 0:
            if (*p == ' ') {
                m = 10;
                putchar('\n');
            } else {
                putchar(*p);
            }
            break;
        case 10:
            if (*p == ' ') {
                // pass
            } else {
                m = 0;
                p -= 1;
            }
            break;
        }
    }

    return 0;
}

上記のコードを実行すると↓の結果になります。

cat
dog
bird

ちなみにこの解析だと文字列の先頭に半角スペースがある場合に変な挙動をします。
今回は簡便さのためにそのままにしています。

↑のコードの変数mが状態を表す変数です。
状態は整数の0または10で表現されます。
状態が0の時は半角スペースを監視し、他の文字は出力します。
状態が10の時は半角スペースを無視し、他の文字が来たら状態を0に戻します。

このように状態を複数持たせると複雑な処理を分割して書くことができます。
処理を分割するというのは難しい処理を簡単にするということです。
このように状態遷移は非常に使えるテクニックです。おすすめ。

mystrtokでパースする方法

strtok()は内部でstaticな変数を使っているので非スレッドセーフになるという欠点があります。
これを改善したmystrtok()を作ってみました。
コードはMITライセンスです。バグもあるかもしれないので使う場合は注意してください。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

/**
 * 引数のstrを破壊的に変更し、トークンを格納した動的な配列を返す
 * 
 * @param[in|out] str   分割対象文字列
 * @param[in]     seps  区切り文字
 * @return              動的配列(freeが必要)
 */
char **mystrtok(char *str, const char *seps) {
    if (!str || !seps) {
        return NULL;
    }

    // 文字列の長さを得る
    size_t len = strlen(str);

    // 動的配列を作る
    size_t capa = 2;
    size_t byte = sizeof(char *);
    size_t size = byte * capa + byte;  // +byteはNULL番兵分
    char **ary = malloc(size);  
    if (!ary) {
        return NULL;
    }
    memset(ary, 0, size);

    // 文字列の区切り文字を'\0'で埋める
    // つまり引数のstrを破壊的に変更する
    for (size_t i = 0; i < len; i += 1) {
        if (strchr(seps, str[i])) {
            str[i] = '\0';
        }
    }

    // 配列を伸縮するマクロ
#define resize() \
    capa *= 2; \
    size = byte * capa + byte; \
    char **tmp = realloc(ary, size); \
    if (!tmp) { \
        free(ary); \
        return NULL; \
    } \
    ary = tmp; \
    ary[capa] = NULL; \

    // ヘッドを見つけるマクロ
#define findhead() \
    head = NULL; \
    for (; i < len; i += 1) { \
        if (str[i]) { \
            head = &str[i]; \
            break; \
        } \
    } \

    char *head = NULL;  // 格納するトークンのヘッド
    size_t i = 0;
    size_t ary_len = 0;  // 配列aryの長さ

    // ヘッドを見つける
    findhead();

    // 配列にトークンを格納する
    for (; i < len; i += 1) {
        if (str[i]) {
            continue;
        }

        if (head) {
            if (ary_len >= capa) {
                // 配列の容量がいっぱいだったら配列を伸縮する
                resize();
            }

            ary[ary_len++] = head;  // トークンを格納
            ary[ary_len] = NULL;  // NULL番兵

            // ヘッドを見つける
            findhead();
            i -= 1;            
        }
    }

    if (head) {
        if (ary_len >= capa) {
            // 配列の容量がいっぱいだったら配列を伸縮する
            resize();
        }
        ary[ary_len++] = head;  // トークンを格納
        ary[ary_len] = NULL;  // NULL番兵
    }

    return ary;
}

int main(void) {
    char **toks;

    char str0[] = "cat dog  bird, pig";
    toks = mystrtok(str0, " ,");
    assert(toks);
    assert(strcmp(toks[0], "cat") == 0);
    assert(strcmp(toks[1], "dog") == 0);
    assert(strcmp(toks[2], "bird") == 0);
    assert(strcmp(toks[3], "pig") == 0);
    assert(toks[4] == NULL);
    free(toks);

    char str1[] = "  cat dog bird ";
    toks = mystrtok(str1, " ");
    assert(toks);
    assert(strcmp(toks[0], "cat") == 0);
    assert(strcmp(toks[1], "dog") == 0);
    assert(strcmp(toks[2], "bird") == 0);
    assert(toks[3] == NULL);
    free(toks);

    char str2[] = "     cat ,:dog :,   bird   aaa bbb ccc ddd eee";
    toks = mystrtok(str2, " ,:");
    assert(toks);
    assert(strcmp(toks[0], "cat") == 0);
    assert(strcmp(toks[1], "dog") == 0);
    assert(strcmp(toks[2], "bird") == 0);
    assert(strcmp(toks[3], "aaa") == 0);
    assert(strcmp(toks[4], "bbb") == 0);
    assert(strcmp(toks[5], "ccc") == 0);
    assert(strcmp(toks[6], "ddd") == 0);
    assert(strcmp(toks[7], "eee") == 0);
    assert(toks[8] == NULL);
    free(toks);

    char str3[] = "";
    toks = mystrtok(str3, " ");
    assert(toks);
    assert(toks[0] == NULL);
    free(toks);

    char str4[] = "  ";
    toks = mystrtok(str4, " ");
    assert(toks);
    assert(toks[0] == NULL);
    free(toks);

    char str5[] = "cat";
    toks = mystrtok(str5, " ");
    assert(toks);
    assert(strcmp(toks[0], "cat") == 0);
    assert(toks[1] == NULL);
    free(toks);

    char str6[] = " cat ";
    toks = mystrtok(str6, " ");
    assert(toks);
    assert(strcmp(toks[0], "cat") == 0);
    assert(toks[1] == NULL);
    free(toks);

    return 0;
}

main()関数内にはassert()で単体テストを書いています。
単体テストとは関数などが正しく動作するかチェックすることを言います。

このmystrtok()は第1引数の文字列を破壊的に変更する点はstrtok()と同じです。
違いは結果を動的配列で返す点です。

動的配列はポインタ配列になっていて、各要素には第1引数の文字列内の各トークンが保存されています。
動的配列にはNULL番兵も格納されているのでfor文で回すこともできます。

この関数は最初に引数の文字列strの区切り文字部分を\0で埋めます。
こうすると文字列内を\0で区切ることができます。
\0で区切ると各トークンは独立した文字列として扱うことができます。

動的配列ではmalloc()realloc()を使っています。
malloc()で最初にメモリを確保して、realloc()で配列を伸縮しています。

mystrtok()が返す動的配列は動的なメモリ確保で作成されています。
そのためこの動的配列はfree()で解放する必要があります。

おわりに

今回はC言語で文字列の単語を抽出する処理を解説しました。
簡易的にはstrtok()が一番楽です。
高度な処理が必要な場合は外部ライブラリか状態遷移などを使った方法を検討してみてください。

(^ _ ^)

文字列のパースはおもしろいな

(・ v ・)

けっこうシビアな処理だよね



この記事のアンケートを送信する