状态机：基础二 （ZT）

转载时请注明出处和作者联系方式
文章出处：http://www.limodev.cn/blog
作者联系方式：李先静

系统程序员成长计划-文本处理(一)

状态机(2)

o 用有穷状态机解一道面试题。

刚毕业的时候，我到一家外企面试，面试题里有这样一道题：

统计一篇英文文章里的单词个数。

有多种方法可以解这道题，这里我们选择用有穷状态机来解，做法如下：

先把这篇英文文章读入到一个缓冲区里，让一个指针从缓冲区的头部一直移到缓冲区的尾部，指针会处于两种状态：“单词内”或“单词外”，加上后面提到的初始状态和接受状态，就是有穷状态机的状态集。缓冲区中的字符集合就是有穷状态机的字母表。

如果当前状态为“单词内”，移到指针时，指针指向的字符是非单词字符(如标点和空格)，那状态会从“单词内”转换到“单词外”。如果当前状态为“单 词外”， 移到指针时，指针指向的字符是单词字符(如字母)，那状态会从“单词外”转换到“单词内”。这些转换规则就是状态转换函数。

指针指向缓冲区的头部时是初始状态。

指针指向缓冲区的尾部时是接受状态。

每次当状态从“单词内”转换到“单词外”时，单词计数增加一。
这个有穷状态机的图形表示如下：

下面我们看看程序怎么写：

int count_word(const char* text)
{
/*定义各种状态，我们不关心接受状态，这里可以不用定义。*/
enum _State
{
STAT_INIT,
STAT_IN_WORD,
STAT_OUT_WORD,
}state = STAT_INIT;

int count = 0;
const char* p = text;

/*在一个循环中，指针从缓冲区头移动缓冲区尾*/
for(p = text; *p != '/0'; p++)
{
switch(state)
{
case STAT_INIT:
{
if(IS_WORD_CHAR(*p))
{
/*指针指向单词字符，状态转换为单词内*/
state = STAT_IN_WORD;
}
else
{
/*指针指向非单词字符，状态转换为单词外*/
state = STAT_OUT_WORD;
}
break;
}
case STAT_IN_WORD:
{
if(!IS_WORD_CHAR(*p))
{
/*指针指向非单词字符，状态转换为单词外，增加单词计数*/
count++;
state = STAT_OUT_WORD;
}
break;
}
case STAT_OUT_WORD:
{
if(IS_WORD_CHAR(*p))
{
/*指针指向单词字符，状态转换为单词内*/
state = STAT_IN_WORD;
}
break;
}
default:break;
}
}

if(state == STAT_IN_WORD)
{
/*如果由单词内进入接受状态，增加单词计数*/
count++;
}

return count;
}

用状态机来解这道题目，思路清晰，程序简单，不易出错。

这道题目只是为了展示一些奇技淫巧，还是有一些实际用处呢？回答这个问题之前，我们先对上面的程序做点扩展，不只是统计单词的个数，而且要分离出里面的每个单词。

int word_segmentation(const char* text, OnWordFunc on_word, void* ctx)
{
enum _State
{
STAT_INIT,
STAT_IN_WORD,
STAT_OUT_WORD,
}state = STAT_INIT;

int count = 0;
char* copy_text = strdup(text);
char* p = copy_text;
char* word = copy_text;

for(p = copy_text; *p != '/0'; p++)
{
switch(state)
{
case STAT_INIT:
{
if(IS_WORD_CHAR(*p))
{
word = p;
state = STAT_IN_WORD;
}
break;
}
case STAT_IN_WORD:
{
if(!IS_WORD_CHAR(*p))
{
count++;
*p = '/0';
on_word(ctx, word);
state = STAT_OUT_WORD;
}
break;
}
case STAT_OUT_WORD:
{
if(IS_WORD_CHAR(*p))
{
word = p;
state = STAT_IN_WORD;
}
break;
}
default:break;
}
}

if(state == STAT_IN_WORD)
{
count++;
on_word(ctx, word);
}

free(copy_text);

return count;
}

状态机不变，只是在状态转换时，做是事情不一样。这里从“单词内”转换到其它状态时，增加单词计数，并分离出当前的单词。至于拿分离出的单词来做什么，由传入的回调函数决定，比如可以用来统计每个单词出现的频率。

但如果讨论还是限于英文文章，这个程序的意义仍然不大，现在来做进一步扩展。我们考虑的文本不再是英文文章，而是一些文本数据，这些数据由一些分隔符分开，我们把数据称为token，现在我们要把这些token分离出来。

typedef void (*OnTokenFunc)(void* ctx, int index, const char* token);

#define IS_DELIM(c) (strchr(delims, c) != NULL)
int parse_token(const char* text, const char* delims, OnTokenFunc on_token, void* ctx)
{
enum _State
{
STAT_INIT,
STAT_IN,
STAT_OUT,
}state = STAT_INIT;

int count = 0;
char* copy_text = strdup(text);
char* p = copy_text;
char* token = copy_text;

for(p = copy_text; *p != '/0'; p++)
{
switch(state)
{
case STAT_INIT:
case STAT_OUT:
{
if(!IS_DELIM(*p))
{
token = p;
state = STAT_IN;
}
break;
}
case STAT_IN:
{
if(IS_DELIM(*p))
{
*p = '/0';
on_token(ctx, count++, token);
state = STAT_OUT;
}
break;
}
default:break;
}
}

if(state == STAT_IN)
{
on_token(ctx, count++, token);
}

on_token(ctx, -1, NULL);
free(copy_text);

return count;
}

用分隔符分隔的文本数据有很多，如：

环境PATH，它由‘:’分开的多个路径组成。如：
/usr/lib/qt-3.3/bin:/usr/kerberos/bin:/backup/tools/jdk1.5.0_18/bin/:/usr/lib/ccache:/usr/local/bin:/bin:/usr/bin:/home/lixianjing/bin

文件名，它由‘/’分开的路径组成。如：
/usr/lib/qt-3.3/bin

URL中的参数，它‘&’分开的多个key/value对组成。
hl=zh-CN&q=limodev&btnG=Google+搜索&meta=&aq=f&oq=

所有这些数据都可以用上面的函数处理，所以这个小函数是颇具实用价值的。