次へ: 7 パターンマッチ中心のアルゴリズム 上へ: C のソースからプロトタイプ宣言を作成 前へ: 5 getline (PDF ファイル: awktg.pdf)


6 単純なアルゴリズム

まずは、今回のプログラムを最も単純に考えてみることにします。
(1) 1 行入力する (暗黙の getline)
(2) 現在行が「ア」の行かチェック
  (3) 「ア」ならば、その行を保存して
  (4) その行が「イ」であるかチェック
    (5) 「イ」ならば、次の行を取得し それが「エ」であるかチェック
      (6) 「エ」ならば、保存したものに `;' をつけて出力する
      (7) 「エ」でなければ、(2) に戻る
    (8) (4) が「イ」でなければ「オ」であるかチェック
      (9) 「オ」ならば、(1) に戻る
    (10) 「オ」でなければ、次の行を取得し それが「ウ」であるかチェック  
        (11) 「ウ」ならば、その行を保存し (4) に戻る
        (12) 「ウ」でなければ、(2) に戻る
  (13) (2) が「ア」でなければ、(1) に戻る
これをフローチャートにしたのが図 1 です。
図 1: 単純なアルゴリズムのフローチャート
\includegraphics[width=0.4\textwidth]{flow2.eps}
(7) と (12) のところでは、新しい行を取得するのではなく、 現在持っている直前に取得した行に対して「ア」のチェックを行うため、 先頭、すなわち暗黙の getline の前に戻るのではなく、 getline と「ア」の間に戻るようにしています。

これを AWK の疑似コード (おおまかなコード) として書いてみると、 例えば次のようになります。

  {
      while(1){
          if(!「ア」) next
          (リセットして保存)
          while(1){
              if(「イ」){
                  getline
                  if(「エ」){ (出力); next }
                  else break
              }
              else if(「オ」) next
              else{
                  getline
                  if(!「ウ」) break
                  (保存)
              }
          }
      }
  }
このコードでポイントとなるのは、2 つの while 文です。 ``while(1)'' は、C 言語でもよく使われる手法ですが、 条件判断が常に真 (つまり 1) であるループなので、 無限ループを作っていることになります。

「ア」の条件判断をこの while ループの外に出して先頭の行に書いてしまうと、 「ア」の判断の前には必ず行の取得 (暗黙の getline) が 行われることになってしまい、(7) や (12) を実現できません。 よって、それを while(1) で囲むことで 行を取得せずに「ア」の判断部分に戻れるようにしていて、 行を取得してから「ア」の判断をしたい場合は next を使うようにして その while 文から抜け出すようにしています。

2 つ目の while(1) 文は、「ウ」のループ構造の実現のためです。 フローチャートを見ればわかりますが、 「ウ」で保存した後は次の行や「ア」の上に戻るのではなく、 「イ」の上に戻りますので、この流れがひとつのループ構造になっています。 よって、そこをなんらかのループとして書く必要があるわけです。 ここでは、「ウ」でない場合にこの 2 つ目の while ループから抜けて 「ア」の上に戻る、つまり (12) を実現するために break 文を使って 内側の while ループから抜け出しています。

「イ」の後の処理である (5),(6),(7) も while ループの中に書きましたので、 (7) では break 文で内側のループから抜けるようにしていますが、 「イ」だった場合にまず break して内側の while ループから抜け、 その外でその後の処理 (5),(6),(7) の処理を書く、という手もあります。 ただし、その場合その部分は、(12) で break したのではないことを 区別するためのコードを書く必要があります。


次へ: 7 パターンマッチ中心のアルゴリズム 上へ: C のソースからプロトタイプ宣言を作成 前へ: 5 getline
竹野茂治@新潟工科大学
2006年6月22日