用有穷自动机解一道面试题.doc

用有穷自动机解一道面试题
题目的要求是：一个字符串由多个单词组成，这些单词由一个或者连连续多个空格分隔开，请写一个程序统计输入的字符串有多少个单词。
这个题目很简单，可能有N种方法可以解决它。把它用来做实例，并非是要想说明DFA的功能强大，而是因为它是一个说明DFA的好例子。这个DFA：
字母表：英文字母和空格。
状态：起始状态、单词状态、空格状态和接受状态。
转换规则：
起始状态下读到非空格，进入单词状态。
单词状态下读到空格，进入空格状态。
空格状态下读到非空格，进入单词状态。
在起始状态、单词状态和空格状态下读到’/0’，进入结束状态。
每次进入单词状态，单词数计数加1。
实现代码如下：
//Build: gcc -DDEBUG -g countwords.c -o cw.exe
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int CountWords(const char* pszStr)
{
         enum
         {
                  STAT_START,
                  STAT_IN_WORD,
                  STAT_IN_SPACE
         }eState = STAT_START;
         int nWordsNr = 0;
         const char* p = pszStr;
         assert(pszStr != NULL);

         while(*p != '/0')
         {
                  switch(eState)
                   {
                            case STAT_START:
                                     {
                                               if(*p == ' ')
                                               {
                                                        eState = STAT_IN_SPACE;
                                               }
                                               else
                                               {
                                                        nWordsNr++;
                                                        eState = STAT_IN_WORD;
                                               }
                                               break;
                                     }
                            case STAT_IN_WORD:
                                     {
                                               if(*p == ' ')
                                               {
                                                        eState = STAT_IN_SPACE;
                                               }
                                               break;
                                     }
                            case STAT_IN_SPACE:
                                     {
                                               if(*p != ' ')
                                               {
                                                        nWordsNr++;
                                                        eState = STAT_IN_WORD;
                                               }
                                               break;
                                     }
                            default:break;
                   }

                   p++;
         }

         return nWordsNr;
}

int main(int argc, char* argv[])
{
         int nRet = 0;
         if(argc == 2)
         {
                   nRet = CountWords(argv[1]);
                  printf("WordsNr=%d/n", nRet);
         }
         else
         {
                  printf("Usage: %s [str]/n", argv[1]);
                   nRet = 0;
         }
         return nRet;
}