C言語 標準関数 | 応用 | サンプル

標準関数
構文
応用

管理人

プライバシーポリシー


パターンマッチングによるlsコマンドの実現

C言語で文字列があるパターンにマッチングするかをチェックする手法を紹介します。

マッチングと言えば、正規表現を思い浮かべると思いますが、今回はC言語でそれを実現します。

例題として、unixやlinuxでおなじみのlsコマンドのワイルドカード処理を考えます。

lsコマンドのワイルドカード処理(マッチング機能)を実際に打鍵して確認すると、以下のような仕様になっています。(全角は考慮していません。半角のみです。)
C言語の特性としてNULL(\0)で文字列の終わりを認識しますので、NULLは1文字としては扱いません。

1.任意の1文字は同じ1文字のみにマッチする。(当たり前ですが)
2.'?'は任意の1文字にマッチする。
3.'*'は任意の0文字以上の文字にマッチする。

他にも機能があるかもしれませんが、とりあえず上記1~3を実現してみます。

実現に際しては、再帰によるバックトラック機能を使用します。
バックトラックとは、ある事象をチェックしてエラー(FALSE)だったら、元に戻って次の事象をチェックする行為を指します。

動作イメージを羅列してみます。

・'abcde.txt'と言うファイル名にマッチするのは
  → '*'、'?bcde.txt'、'*.txt'
    、'*************'、'*******?????????******'
    などです。

もうお分かりだと思いますが、マッチする対象は無限にあります。その理由は、'*'は文字以上の文字とマッチするからです。

・'abcde.txt'と言うファイル名にマッチしないのは
  → 'a'、'??bcde.txt'、'*****?????.????*****'
    などです。

同様に、マッチしない対象も無限にあります。

前置きはこのくらいにして実際のソースコードを見て下さい。
尚、プログラムの起動引数には、各々必ず1文字以上を指定して下さい。

プログラム(仮にprog_idとします)を実行するには以下のようにして下さい。
シングルクォート(')はダブルクォート(")でもOKです。

prog_id 'a?*.txt' 'abcde.txt'

ソースコード

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

#define BOOL int
#define TRUE 1
#define FALSE 0

/* マッチング関数 */
BOOL match( char * s1 , char * s2 ) {

  /* 収束条件 ① */
  if( s1[0] == '\0' && s2[0] == '\0' ) {
    return TRUE;
  }

  /* '?'の処理 */
  if( s1[0] == '?' ) {
    if( s2[0] == '\0' ) {
      /* 収束条件 ④ */
      return FALSE;
    }
    else {
      /* '?'に対して1文字マッチしたので次の文字へ ⑤ */
      return match( &s1[1] , &s2[1] );
    }
  }

  /* '*'の処理 */
  if( s1[0] == '*' ) {
    if( s2[0] == '\0' ) {
      /* '*'は0文字以上とマッチするので ⑥ */
      return match( &s1[1] , &s2[0] );
    }
    else {
      /* '*'が1文字にマッチしたかチェック */
      if( match( &s1[1] , &s2[0] ) == TRUE ) {
        /* 収束条件 ⑦ */
        return TRUE;/* マッチしたのでTRUE */
      }
      else {
        /* アンマッチだったのでバックトラック ⑧ */
        return match( &s1[0] , &s2[1] );
      }
    }
  }

  /* 同一文字同士で1文字マッチしたので次へ ③ */
  /* (ここでは既に'?'や'*'は排除されている) */
  if( s1[0] == s2[0] ) {
    return match( &s1[1] , &s2[1] );
  }

  /* 収束条件 ② */
  /* (異なる文字同士で1文字アンマッチだったのでFALSE) */
  return FALSE;

}

/* メイン関数 */
int main( int argc , char* argv[] ) {

  char * str[2];
  int i;

  /* 起動引数の個数チェック */
  /* argv[0]→起動プログラム(自分自身) */
  /* argv[1]→第1引数 */
  /* argv[2]→第2引数 */
  if( argc != 3 ) {
    printf( "引数エラー\n" );
    return -1;
  }

  /* 起動引数から比較対象を取得 */
  for( i=0 ; i<2 ; i++ ) {
    str[i] = ( char * )malloc( strlen( argv[i+1] ) + 1 );
    if( str[i] == NULL ) {
      printf( "領域確保エラー\n" );
      return -1;
    }
    strcpy( str[i] , argv[i+1] );
  }

  /* 結果の表示 真であればTRUE、偽であればFALSE */
  /* (これを三項演算と言う) */
  printf( "%s\n"
       , match( str[0] , str[1] ) ? "TRUE":"FALSE" );

  /* 確保領域を開放 */
  for( i=0 ; i<2 ; i++ ) free(( void * )str[i] );

  return 0;
}

実行結果の例(プログラムIDはprog_id)

prog_id 'a?*.txt' 'abcde.txt'
TRUE

ソースコードの解説

この手の処理の考え方ですが、一般条件('?'や'*'以外)と特殊条件('?'や'*')に場合分けします。

場合分けの第1として、一般条件('?'や'*'以外)について、最も単純な「TRUEを返す条件」と「FALSEを返す条件」を考えます。ソースコードでは各々、①②が該当します。TRUEやFALSE以外は継続(③が該当)します。継続とは再帰することを指します。

(a) TRUEを返す条件 → ①
(b) FALSEを返す条件→ ②
(c) 継続する条件 → ③

場合分けの第2として、特殊条件('?'や'*')の'?'について考えます。'?'は任意の1文字に対応、つまり1:1の対応なので簡単です。

(d) FALSEを返す条件 → ④
(e) 継続する条件 → ⑤

※TRUEを返す条件はありません。これは、'?'に対応するのは任意の1文字であり、以降に文字があるかどうかはこの時点では確定できないからです。従って、ここでは'?'に対応する文字が存在しない(NULLは文字として扱わない)場合のみにFALSEを返します。

次に'*'について考えます。'*'は任意の0文字以上の文字に対応、つまり1:n(n≧0)なので厄介です。
まず、第2引数s2がNULLの場合は'*'は0文字とマッチしているので継続させます(⑥)。
次に、第2引数s2がNULL以外の場合は将来を考えます。つまり、試しにやってみてうまく行ったらTRUEを返し(⑦)、ダメだったら別の方法を試行(⑧)する。別の方法を試行する、つまりバックトラックさせる。

(f) 第2引数s2がNULLの場合 → 継続する条件 → ⑥
(g) 第2引数s2がNULL以外の場合 → 将来がTRUE → TRUEを返す条件 → ⑦ → 将来がFALSE → 継続する条件 → ⑧

注意することは、'*'に関する処理で、処理途中でTRUEになった時点でmatch関数の最終的な戻り値はTRUEです。継続はせず、FALSEになる条件は探しません。
しかし、処理途中でFALSEになった場合は、バックトラック(再試行)してTRUEになる条件を探します。つまり継続するのです。継続中にTRUEになった時点で最終的な戻り値はTRUEになり、最終的にTRUEにならなかった場合のみ、FALSEの判定を下すのです。

バックトラックするには、その戻り位置を覚えておかなければなりませんが、(将来を)試行することにより必然的に戻り位置が保存されています。

以上で解説を終わります。拙い解説ですが、お分かり頂けたでしょうか?
初めての方にとっては、かなり難しかったと思いますが、いつかは役に立つかも知れません。
同様なバックトラックについては、書籍などでは「エイトクイーン問題」や「人食い人種と宣教師」などと紹介されているので参考になると思います。


Copyright © 2008-2015 http://hitorilife.com All Rights Reserved.