[Altorithm] 有限状态机(FSM)实现字符串分解 (ZT)

web_surf

VC++2008下写的，因此用到了CString，同时Potlet是我自己写了一个容器，真的使用的时候可以换成STL容器例如vector<CString>。
改程序读取一个source字符串，里面包含若干逗号分隔符，希望自动分解source字串，得到若干子串，放置到Potlet中，虽然功能非常简单，但 是依然包含了很多很多情况，比如多个逗号，逗号在source头部，逗号在source尾部。。。如果用传统的方法编写程序，将会变得很复杂，并且容易出 错。传统算法的流程图：

如果采用状态机的思想来实现，则会变得非常简单：


其中NORMAL表示读到的是一个正常字符，COMA表示读到的是一个逗号，ZERO表示读到的是'\0'字符，这也是最终状态。程序仅需列举出所有的状态(state)和路径(path)，并且进行合适地处理就可以了。
代码如下：

//代码开始
#define NORMAL 0
#define COMA 1
#define ZERO 2

int getState(char c)
{
    if(c=='\0')
        return ZERO;
    if(c==',')
        return    COMA;
    return NORMAL;  
}

/*
we push subStr to Potlet and clear subStr only when the state change from NORMAL to COMA(path B) or ZERO(path E)
*/
Potlet getPotletString(CString source)
{
    Potlet potlet;//the potlet to save subStrs
    //if source is null,return a potlet contains nothing
    if (len<=0)
        return potlet;
       
    int state;//show the state
    char chr[]=source;//get a char[] type source,without extra data
    CString subStr="";//buffer of sub String

    state=getState(chr[0]);//get initial state,of cause the chr is not null,so we can use chr[0]
    int i=0;//show the location in chr
   
    //FSM runs here
    while(state!= ZERO)
    {
        switch(state)
        {
        //it's NORMAL
        case NORMAL:
            subStr+=chr[i];//add chr[i] to subStr
            //move
            i++;
            //get next state
            state=getState(chr[i]);
            switch(state)
            {
            //path A
            case NORMAL:
                //do nothing
                break;
            //path B
            case COMA:
                potlet.push_back(subStr+'\0');
                subStr="";
                break;
            //path E
            case ZERO:
                potlet.push_back(subStr+'\0');
                break;
            }
            break;
       
        //it's a comma
        case COMA:
            //move
            i++;
            //get next state
            state=getState(chr[i]);
            switch(state)
            {
                //path C
                case NORMAL:
                //do nothing
                break;
                //path D
                case COMA:
                //do nothing
                break;
                //path F
                case ZERO:
                //do nothing
                break;
            }
           
            break;
        }//end switch
    }
    //the state is ZERO
    return potlet;
}
//代码结束

AlbertDiao

转载请注明出处！原创链接如下：
http://hi.baidu.com/albertdiao/b ... b0d53b5882dde3.html