前几天突然想写一个正则表达式引擎,于是计划用5个小时搞定一个一般的RegexEngine.
不过断断续续加起来严重超时,写了十几个小时,大体功能完成。
写一个正则表达式需要考虑的内容还是不少的。

比如:
0 词法分析：涉及到怎么划分原子粒度,我把/[A..Z1..5_]/作为一个词法元素,另外用一张表索引子词法元素
1 语法分析：直接一个函数递归消化掉所有分析并转化为Epsilon-NFA，其中*号要避免空回路。
2 表达式匹配：同样一个递归消化掉所有内容,E-NFA处理空串匹配时要单独处理。

由于用到了自己上一年写的泛化adt::graph类,所以图结构基本没花很多时间，给graph扩展了一个E-NFA匹配的功能。

700行的ProBetaMinus版本,到完整的Beta版本,估计要增加200行代码（加入重复描述符检测和{m,n},{m,n}处理估计要用到递归+函数内临时堆栈）.此外我会对自己的adt::graph类做一个优化,确保其更好的支持Regex.

用了几十个case,目前没发现Bug,不过随着以后使用的过程,肯定会出现不同的BUG。

/*regex.h :vgl::regex*/
/*----------------------------------------------------------------------------
Simplex v1.2
Developer: Zblc
vgl::regex


enumes:


classes:
AtomToken                            ：原子词
Regex                               ：正则表达式分析类

macros:
MAX_SUB_ROW                            ：[]的最大数
MAX_SUB_COW                         ：[]中原子字符的最大数
MAX_TOKEN                           ：最大接受的原子字符数
CAPA_LIST                           ：调试用
CAPA_LIST_LETTER                    ：调试用
namespace variable:
AtomToken subList[MAX_SUB_ROW][MAX_SUB_COW];   ：存储正则表达式中每个[]中原子字符
static int subListLen[MAX_SUB_ROW];  ：存储正则表达式中每个[]中原子字符个数
static int subLen;                   ：存储正则表达式中[]的个数

includes:
graph.h                               ：VGL::ADT::有向图

-------------------------------------------------------------------------------*/




#ifndef REGEX__
#define REGEX__

#include "graph.h"

namespace simplex
{
    typedef  char AtomChar;
    enum AtomType{AtomNormChar,AtomRangeLeft,AtomRangeRight,AtomRangeOne,AtomRangeBoth,AtomLeftMB,
        AtomRightMB,AtomLeftBB,AtomRightBB,AtomLeftSB,AtomRightSB,
        AtomNormESC,AtomMoreOne,AtomMoreZero,AtomZeroOne,AtomNot,
        AtomBegin,AtomEnd,AtomDigit,AtomNotDigit,AtomLetter,AtomNotLetter,
        AtomAny,AtomLetterRange,AtomDigitRange,AtomMu,AtomOr,AtomOrList,AtomNotAndList};

#define CAPA_LIST 35
#define CAPA_LIST_LETTER 25
    char list[CAPA_LIST][CAPA_LIST_LETTER]={"AtomNormChar","AtomRangeLeft","AtomRangeRight","AtomRangeOne","AtomRangeBoth","AtomLeftMB",
        "AtomRightMB","AtomLeftBB","AtomRightBB","AtomLeftSB","AtomRightSB",
        "AtomNormESC","AtomMoreOne","AtomMoreZero","AtomZeroOne","AtomNot",
        "AtomBegin","AtomEnd","AtomDigit","AtomNotDigit","AtomLetter","AtomNotLetter",
        "AtomAny","AtomLetterRange","AtomDigitRange","AtomMu","AtomOr","AtomOrList","AtomNotAndList"};

#define MAX_SUB_ROW 50
#define MAX_SUB_COW 30
#define MAX_TOKEN 200

    static int subListLen[MAX_SUB_ROW];
    static int subLen;
    class AtomToken;

    class AtomToken
    {
    public:

        AtomChar c[3];
        AtomType type;
        int subIndex;

        AtomToken()
        {    
            memcpy(c,"",3);
            type=AtomNormChar;
            subIndex=0;

        }
        ~AtomToken()
        {
            subIndex=0;
        }
        AtomToken* operator=(AtomToken& _copy)
        {

            memcpy(c,_copy.c,3*sizeof(char));
            type=_copy.type;

            subIndex=_copy.subIndex;
            return this;

        }
        int operator ==(AtomToken & _token)
        {

            AtomToken* b,*ob;

            if(type==AtomNormChar)
            {
                b=&_token;
                ob=this;
            }else
            {
                b=this;
                ob=&_token;
            }

            if(b->type==AtomMu)
            {

                return 2;
            }



            switch(b->type)
            {
            case AtomNotAndList:
            case AtomOrList:


                for(int j=0;j!=subListLen[b->subIndex];j++)
                {

                    if(subList[b->subIndex][j]==*ob)
                        return 1;
                }
                return 0;
            case AtomAny:
                return ob->type==AtomNormChar;
            case AtomNormChar:
                return b->c[0]==ob->c[0];
            case AtomNormESC:
                switch(b->c[0])
                {
                case 'd':
                    return ob->c[0]>='0'&&ob->c[0]<='9';
                case 'D':
                    return ob->c[0]<'0'||ob->c[0]>'9';
                case 'b':
                    return (ob->c[0]>='a'&&ob->c[0]<='z')||(ob->c[0]>='A'&&ob->c[0]<='Z');
                case 'B':
                    return (ob->c[0]<'a'||ob->c[0]>'z')&&(ob->c[0]<'A'||ob->c[0]>'Z');


                }
                return _token.c[0]==c[0];

            case AtomDigitRange:
                return ob->c[0]>=b->c[0]&&ob->c[0]<=b->c[1];
            case AtomLetterRange:

                return ob->c[0]>=b->c[0]&&ob->c[0]<=b->c[1];

            default:
                return 0;
            }
        }

    }subList[MAX_SUB_ROW][MAX_SUB_COW];

    class Regex /* Regex Analyser :Scanning and Grammar,Match*/
    {
    protected:
        AtomToken tokens[MAX_TOKEN];
        adt::graph<int,AtomToken> nfa;/* Epsilon-NFA */
        int len;
        int isDigit(char c)
        {
            return c<='9'&&c>='0';
        }
        int isLetter(char c)
        {
            return (c<='z'&&c>='a')||(c<='Z'&&c>='A');
        }
        int getFirstNum(char * _buf,int & _len)
        {
            int i,num=0;
            for(i=0;isDigit(_buf[i]);i++);
            _len=i;
            i--;
            for(int j=0;i!=-1;i--,j++)
            {

                num+=(_buf[i]-'0')*atom::pow10(j);
            }
            return num;

        }
        AtomToken* buf_tokens;
    public:
        Regex()
        {
            subLen=0;
        }
        ~Regex()
        {
            if(!buf_tokens)
                delete []buf_tokens;
        }
        void atomParse(char* _buf)
        {

            int buf_len=atom::lenof(_buf),temp_len=0;
            len=0;
            AtomToken _list[MAX_SUB_COW];
            int lenList=0;
            for(int i=0;i!=buf_len;)
            {
                switch(_buf[i])
                {
                case '^':

                    tokens[len].c[0]='^';
                    if(i==0)
                        tokens[len].type=AtomBegin;
                    else
                        tokens[len].type=AtomNot;
                    i++;
                    break;
                case '.':
                    tokens[len].c[0]='.';
                    tokens[len].type=AtomAny;

                    i++;
                    break;
                case '|':
                    tokens[len].c[0]='|';
                    tokens[len].type=AtomOr;

                    i++;
                    break;

                case '+':
                    tokens[len].c[0]='+';
                    tokens[len].type=AtomMoreOne;

                    i++;
                    break;

                case '*':
                    tokens[len].c[0]='*';
                    tokens[len].type=AtomMoreZero;
                    i++;
                    break;

                case '?':
                    tokens[len].c[0]='?';
                    tokens[len].type=AtomZeroOne;
                    i++;
                    break;
                case '$':
                    tokens[len].c[0]='$';
                    tokens[len].type=AtomZeroOne;
                    i++;
                    break;
                case '{':

                    if(_buf[i+1]==',')
                    {
                        tokens[len].c[0]=getFirstNum(&_buf[i+2],temp_len);
                        tokens[len].type=AtomRangeRight;
                        i+=temp_len+3;
                        break;
                    }else
                    {
                        tokens[len].c[0]=getFirstNum(&_buf[i+1],temp_len);
                        tokens[len].type=AtomRangeLeft;
                        if(_buf[i+temp_len+1]==',')
                        {
                            if(isDigit(_buf[i+temp_len+2]))
                            {
                                i+=temp_len+2;
                                tokens[len].type=AtomRangeBoth;
                                tokens[len].c[1]=getFirstNum(_buf+i+temp_len+2,temp_len);
                                i+=temp_len;
                                if(_buf[i]=='}')
                                {
                                    i++;
                                    break;
                                }else
                                {
                                    cout<<"Error\n";
                                    break;
                                }

                            }else if(_buf[i+temp_len+2]=='}')
                            {
                                i+=temp_len+3;
                                tokens[len].type=AtomRangeLeft;
                                break;
                            }
                        }else if(_buf[i+temp_len+1]=='}')
                        {
                            i+=temp_len+2;
                            tokens[len].type=AtomRangeOne;
                            break;
                        }

                    }


                case '[':

                    lenList=0;
                    if(_buf[i+1]!='^')
                    {
                        tokens[len].type=AtomOrList;
                    }else
                    {
                        i++;
                        tokens[len].type=AtomNotAndList;
                    }
                    i++;




                    for(;_buf[i]!=']';)
                    {
                        if(isDigit(_buf[i]))
                        {

                            if(i+4<buf_len)
                            {
                                if(_buf[i+1]=='.'&&_buf[i+2]=='.'&&isDigit(_buf[i+3]))
                                {
                                    _list[lenList].c[0]=_buf[i];
                                    _list[lenList].c[1]=_buf[i+3];
                                    _list[lenList].type=AtomDigitRange;
                                    lenList++;
                                    i+=4;
                                    continue;
                                }else
                                {
                                    _list[lenList].c[0]=_buf[i];
                                    _list[lenList].type=AtomNormChar;
                                    lenList++;
                                    i++;
                                    continue;
                                }
                            }else
                            {
                                _list[lenList].c[0]=_buf[i];
                                _list[lenList].type=AtomNormChar;
                                lenList++;
                                i++;
                                continue;
                            }
                        }else if(isLetter(_buf[i]))
                        {

                            if(i+4<buf_len)
                            {

                                if(_buf[i+1]=='.'&&_buf[i+2]=='.'&&isLetter(_buf[i+3]))
                                {

                                    _list[lenList].c[0]=_buf[i];
                                    _list[lenList].c[1]=_buf[i+3];
                                    _list[lenList].type=AtomLetterRange;
                                    lenList++;
                                    i+=4;
                                    continue;
                                }else
                                {
                                    _list[lenList].c[0]=_buf[i];
                                    _list[lenList].type=AtomNormChar;
                                    lenList++;
                                    i++;
                                    continue;
                                }
                            }else
                            {
                                _list[lenList].c[0]=_buf[i];
                                _list[lenList].type=AtomNormChar;
                                lenList++;
                                i++;
                                continue;
                            }
                        }else
                        {
                            switch(_buf[i])
                            {
                            case '\\':
                                i++;
                                switch(_buf[i])
                                {
                                case '|':
                                case '\\':
                                case '(':
                                case ')':
                                case '[':
                                case ']':
                                case '{':
                                case '}':
                                case '*':
                                case '?':
                                case '+':
                                case '^':
                                case '$':
                                case '.':
                                    _list[lenList].c[0]=_buf[i];
                                    _list[lenList].type=AtomNormChar;
                                    lenList++;
                                    i++;
                                    break;
                                case 'd':
                                case 'D':
                                case 'b':
                                case 'B':
                                    _list[lenList].c[0]=_buf[i];
                                    _list[lenList].type=AtomNormESC;
                                    lenList++;
                                    i++;
                                    break;
                                }
                            }
                        }
                    }
                    for(int j=0;j!=lenList;j++)
                    {
                        subList[subLen][j]=_list[j];
                    }
                    tokens[len].subIndex=subLen;
                    subListLen[subLen++]=lenList;
                    ++i;
                    break;

                case '(':
                    tokens[len].c[0]='(';
                    tokens[len].type=AtomLeftSB;
                    i++;
                    break;
                case ')':
                    tokens[len].c[0]=')';
                    tokens[len].type=AtomRightSB;
                    i++;
                    break;
                case '\\':
                    i++;
                    switch(_buf[i])
                    {
                    case '|':
                    case '\\':
                    case '(':
                    case ')':
                    case '[':
                    case ']':
                    case '{':
                    case '}':
                    case '*':
                    case '?':
                    case '+':
                    case '^':
                    case '$':
                    case '.':
                        tokens[len].c[0]=_buf[i];
                        tokens[len].type=AtomNormChar;
                        i++;
                        break;
                    case 'd':
                    case 'D':
                    case 'b':
                    case 'B':
                        tokens[len].c[0]=_buf[i];
                        tokens[len].type=AtomNormESC;
                        i++;
                        break;
                    }
                    break;
                default:


                    tokens[len].c[0]=_buf[i];
                    tokens[len].type=AtomNormChar;
                    i++;
                    break;


                }
                len++;
            }
#ifdef TEST_OPEN_CONSOLE
            /* DEBUG:display all the results */
            cout<<"\nScanning list:\nPrinting format:Token[i](Type,Attribut_1,Attribute_2)\n";
            for(int k=0;k!=len;k++)
            {
                cout<<"Token["<<k<<"]:(\'";
                cout<<list[tokens[k].type]<<"\',\'";
                cout<<tokens[k].c[0]<<"\',\'"<<tokens[k].c[1]<<"\')\t\n";

            }
#endif

        }
        enum NfaStatus{NfaBegin,NfaNormState,NfaEnd};


        void grammarParse(int _index=0,int _deep=0)
        {

            static AtomToken token;

            static int numArc;
            static int lastKey,nowKey,lastBegin;
            static int i;
            if(_index==0)
            {

                lastBegin=1;
                nowKey=1;
                numArc=1;
            }

            int beginNode,endNode;

            nfa.addNode(nowKey,NfaBegin,0);
            beginNode=nowKey++;
            nfa.addNode(nowKey,NfaEnd,0);
            endNode=nowKey++;

            if(_index!=0)
            {
                token.type=AtomMu;
                nfa.addArc(lastKey,beginNode,numArc++,token);
            }
            lastKey=beginNode;




            int temp=0;

            for(i=_index;i!=len;i++)
            {


                switch(tokens[i].type)
                {
                case AtomBegin:
                    break;
                case AtomEnd:
                    break;
                case AtomRightSB:
                    temp=1;
                    if(i+1!=len)
                    {
                        if(tokens[i+1].type==AtomMoreOne)
                        {
                            token.type=AtomMu;
                            nfa.addArc(endNode,beginNode,numArc++,token);
                        }else if(tokens[i+1].type==AtomMoreZero)
                        {
                            token.type=AtomMu;
                            nfa.addNode(nowKey,NfaNormState,0);

                            nfa.addArc(beginNode,endNode,numArc++,token);

                            nfa.addArc(lastKey,nowKey,numArc++,token);

                            nfa.addArc(nowKey,beginNode,numArc++,token);

                            lastKey=nowKey++;

                            //AtomRangeLeft,AtomRangeRight,AtomRangeOne,AtomRangeBoth
                        }else if(tokens[i+1].type==AtomRangeLeft)
                        {

                        }
                    }

                    break;
                case AtomLeftSB:
                    grammarParse(i+1,_deep+1);
                    break;
                case AtomLeftMB:
                    grammarParse(i,_deep+1);
                    break;
                case AtomAny:
                case AtomOrList:
                case AtomNotAndList:
                case AtomNormESC:
                case AtomNormChar:
                    nfa.addNode(nowKey,NfaNormState,0);

                    nfa.addArc(lastKey,nowKey,numArc++,tokens[i]);

                    if(i+1!=len)
                    {
                        if(tokens[i+1].type==AtomMoreOne)
                        {
                            nfa.addArc(lastKey,lastKey,numArc++,tokens[i]);
                        }else if(tokens[i+1].type==AtomMoreZero)
                        {

                            token.type=AtomMu;
                            nfa.addArc(lastKey,nowKey,numArc++,token);
                            nfa.addArc(lastKey,lastKey,numArc++,tokens[i]);
                        }
                    }
                    lastKey=nowKey++;

                    break;


                case AtomOr:


                    token.type=AtomMu;
                    nfa.addArc(lastKey,endNode,numArc++,token);


                    nfa.addNode(nowKey,NfaNormState,0);
                    nfa.addArc(beginNode,nowKey,numArc++,token);
                    lastKey=nowKey++;

                    break;


                default:
                    break;
                }
                if(temp==1)
                    break;

            }
            token.type=AtomMu;
            nfa.addArc(lastKey,endNode,numArc++,token);
            lastKey=endNode;
            lastBegin=beginNode;




        }
        void parse(char* _buf)
        {
            atomParse(_buf);

            grammarParse();

        }

        int match(char* _buf=0)
        {


            int buf_len=atom::lenof(_buf),buf_max,temp;
            buf_tokens=new AtomToken[buf_len];
            for(int i=0;i!=buf_len;i++)
            {
                buf_tokens[i].c[0]=_buf[i];
            }


            /*Restricted in beginning match*/
            buf_max=(tokens[0].type==AtomBegin)?1:buf_len;


            for(int i=0;i!=buf_max;i++)
            {

                if(temp=nfa.isGoEPath(1,buf_tokens,buf_len,i,2))
                {

                    if(tokens[len-1].c[0]=='$')
                    {

                        if(temp==2)
                            return 1;
                        else
                            return 0;
                    }else
                    {
                        return 1;
                    }
                }
            }
            return 0;
        }

    };
}

#endif


另附用到的自己上一年写的adt::graph类.
/*  graph.h :base::adt::graph */

#ifndef GRAPH__

#define GRAPH__

#include "base.h"
#include "vector.h"


namespace adt
{
    using adt::vector;
    template<typename VTypeN,typename VTypeE>
    class graph : public base::adt
    {
    public:
        struct VArc;
        struct VNode;
        struct VArc
        {
            VNode* begin;
            VNode* end;

            int *tag_begin;
            int *tag_end;
            VTypeE weight;

            int tag;/*internal index tag*/
            int key;/*external index tag*/

            VArc()
            {
                tag=0;
                key=0;
            }
            VArc(VNode *_begin,VNode * _end,int _key,int _tag,VTypeE _w)
            {
                begin=_begin;
                end=_end;
                weight=_w;
                tag=_tag;
                key=_key;
                tag_begin=&begin->tag;
                tag_end=&end->tag;
            }
            ~VArc()
            {
                begin=0;
                end=0;
                tag=0;
                key=0;
            }
            /*copy to _arc only by data not adr*/
            void copyTo(VArc * _arc)
            {
                _arc->weight=weight;
                _arc->tag=tag;
                _arc->key=key;
            }
            void setKey(int _key)
            {
                key=_key;
            }
            void setTag(int _tag)
            {
                tag=_tag;
            }
            void setWeight(VTypeE _w)
            {
                weight=_w;
            }
            void setBegin(VNode* _begin)
            {
                begin=_begin;
                tag_begin=&begin->tag;

            }
            void setEnd(VNode* _end)
            {
                end=_end;
                tag_end=&end->tag;
            }
        };
        struct VNode
        {
            vector<VArc*> inArc;
            vector<VArc*> outArc;
            int &inNum;
            int &outNum;

            VTypeN weight;

            int tag;/*internal index tag*/
            int key;/*external index tag*/

            int status;/*node status*/

            /*copy to _arc only by data not adr*/
            void copyTo(VNode * _node)
            {
                _node->weight=weight;
                _node->tag=tag;
                _node->key=key;
                _node->status=status;

            }
            VNode():/*build up ref*/inNum(inArc.n),outNum(outArc.n)
            {
                status=0;
                tag=0;
                key=0;
            }
            VNode(int _key,int _tag,VTypeN _w,int _status):/*build up ref*/inNum(inArc.n),outNum(outArc.n)
            {
                weight=_w;
                status=_status;
                tag=_tag;
                key=_key;
            }
            ~VNode()
            {
                tag=0;
                key=0;
                status=0;
            }
            /*  set key  */
            void setKey(int _key)
            {
                key=_key;
            }
            /*  set tag */
            void setTag(int _tag)
            {
                tag=_tag;
            }
            /*  set weight */
            int setWeight(VTypeN _w)
            {
                weight=_w;
                return 1;
            }
            /*  set status */
            void setStatus(int _status)
            {
                status=_status;
            }

            /* add inArc */
            int addIn(VArc *_inArc )
            {
                if(!_inArc)
                    return 0;
                inArc.push(_inArc);
                //++inNum;
                return 1;
            }
            /* and outArc */
            int addOut(VArc *_outArc )
            {
                if(!_outArc)
                    return 0;
                outArc.push(_outArc);
                //++outNum;
                return 1;
            }

            /* remove inArc by weight */
            int removeInWeight(VTypeE _w)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->weight==_w)
                    {
                        inArc.remove(i);
                        //--inNum;
                        --i;
                    }
                }
                return 1;
            }
            /* remove outArc by weight */
            int removeOutWeight(VTypeE _w)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->weight==_w)
                    {
                        outArc.remove(i);
                        //--outNum;
                        --i;
                    }
                }
                return 1;
            }
            /* remove inArc by tag */
            int removeInTag(int _tag)
            {
                for(int i=0;i!=inArc.n;i++)
                {
                    if(inArc[i]->tag==_tag)
                    {
                        inArc.remove(i);
                        //--inNum;
                        return 1;
                    }
                }
                return 0;
            }
            /* remove outArc by tag */
            int removeOutTag(int _tag)
            {
                for(int i=0;i!=outArc.n;i++)
                {
                    if(outArc[i]->tag==_tag)
                    {
                        outArc.remove(i);
                        //--outNum;
                        return 1;
                    }
                }
                return 0;
            }
            /* remove inArc by key */
            int removeInKey(int _key)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->key==_key)
                    {
                        inArc.remove(i);
                        //--inNum;
                        return 1;
                    }
                }
                return 0;
            }
            /* remove outArc by key */
            int removeOutKey(int _key)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->key==_key)
                    {
                        outArc.remove(i);
                        //--outNum;
                        return 1;
                    }
                }
                return 0;
            }
            /* search inArc by weight */
            VArc* findInWeight(VTypeE _w)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->weight==_w)
                    {
                        return inArc_[i];
                    }
                }
                return 0;

            }
            /* search outArc by weight */
            VArc* findOutWeight(VTypeE _w)
            {
                for(int i=0;i!=outArc.n;i++)
                {
                    if(outArc[i]->weight==_w)
                    {
                        return outArc[i];
                    }
                }
                return 0;

            }
            /* search inArc by tag */
            VArc* findInTag(int _t)
            {
                for(int i=0;i!=inArc.n;i++)
                {
                    if(inArc[i]->tag==_t)
                    {
                        return inArc[i];
                    }
                }
                return 0;

            }
            /* search outArc by tag */
            VArc* findOutTag(int _t)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->tag==_t)
                    {
                        return outArc_[i];
                    }
                }
                return 0;

            }
            /* search inArc by key */
            VArc* findInKey(int _key)
            {
                for(int i=0;i!=inArc_.n;i++)
                {
                    if(inArc[i]->key==_key)
                    {
                        return inArc_[i];
                    }
                }
                return 0;

            }
            /* search outArc by key */
            VArc* findOutKey(int _key)
            {
                for(int i=0;i!=outArc_.n;i++)
                {
                    if(outArc[i]->key==_key)
                    {
                        return outArc_[i];
                    }
                }
                return 0;

            }
        };
        vector<VNode*> allNode;
        vector<VArc*>  allArc;
        int& nodeNum;
        int& arcNum; 
        graph():/*build up ref*/nodeNum(allNode.n),arcNum(allArc.n)
        {

        }
        graph(graph & obj):/*build up ref*/nodeNum(allNode.n),arcNum(allArc.n)
        {
            obj.copyTo(*this);
        }
        int addNode(int _key,VTypeN _w,int _status)
        {



            if(findNodeTag(_key)!=-1)
            {

#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::addNode Function.")
#endif
                    return 0;

            }

            VNode* _node=new VNode;
            /*init data*/
            _node->setKey(_key);
            _node->setWeight(_w);
            _node->setStatus(_status);
            _node->setTag(nodeNum);/*index reciprocally beginning with 0 */
            /*push in index list*/
            allNode.push(_node);
            return 1;
        }
        int setNode(int _key,VTypeN _w,int _status)
        {
            int _tag;

            if((_tag=findNodeTag(_key))==-1)
            {

#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::setNode Function.")
#endif
                    return 0;

            }

            VNode* _node=allNode[_tag];
            /*init data*/
            _node->setWeight(_w);
            _node->setStatus(_status);
            return 1;
        }
        /* switch key to tag */
        int findNodeTag(int _key)
        {
            for(int i=0;i!=allNode.n;i++)
            {
                if(allNode[i]->key==_key)
                {
                    return allNode[i]->tag;
                }
            }
            return -1;
        }
        /* switch key to tag */
        int findArcTag(int _key)
        {
            for(int i=0;i!=allArc.n;i++)
            {
                if(allArc[i]->key==_key)
                {
                    return allArc[i]->tag;
                }
            }
            return -1;
        }
        /* find node by key */
        int findNode(int _key)
        {
            for(int i=0;i!=allNode.n;i++)
            {
                if(allNode[i]->key==_key)
                {
                    return 1;
                }
            }
            return 0;
        }
        /* find arc by key */
        int findArc(int _key)
        {
            for(int i=0;i!=allArc.n;i++)
            {
                if(allArc[i]->key==_key)
                {
                    return 1;
                }
            }
            return 0;
        }
        int isGo(int _key,VTypeE _w,int &_next_key)
        {


            int _tag = findNodeTag(_key);


            if(_tag>=nodeNum||_tag==-1)
            {

#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::isGo function.")
#endif
                    return 0;
            }


            VNode * _node = allNode[_tag];

            VArc* _arc = _node->findOutWeight(_w);

            if(!_arc)
                return 0;
            _next_key = _arc->end->key;
            return 1;
        }
        int getStatus(int _key)
        {
            int _tag = findNodeTag(_key);

            return allNode[_tag]->status;
        }
        /* add arc by begin and end 's key */
        void addArc(int _k_begin,int _k_end,int _key,VTypeE& _w)
        {
            if(findArcTag(_key)!=-1)
            {

#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::addArc function.")
#endif
                    return;

            }
            VArc* _arc=new VArc;
            /* switch key to tag,get begin's and end's adr*/
            int _tag_begin = findNodeTag(_k_begin);
            int _tag_end   = findNodeTag(_k_end);
            VNode* _begin=allNode[_tag_begin];
            VNode* _end  =allNode[_tag_end];
            /*init data*/
            _arc->setBegin(_begin);
            _arc->setEnd(_end);
            _arc->setKey(_key);
            
            _arc->setWeight(_w);
            
            /*index reciprocally beginning with zero */
            _arc->setTag(arcNum);
            /*building begin-end link.*/
            _begin->addOut(_arc);
            _end->addIn(_arc);
            /*push in index list*/
            allArc.push(_arc);


        }
        int setArc(int _key,VTypeE& _w)
        {
            int _tag;
            if((_tag=findArcTag(_key))==-1)
            {

#ifdef TEST_OPEN
                TEST_THROW("Exception in graph.h graph::setArc function.")
#endif
                    return 0;

            }
            VArc* _arc=allArc[_tag];

            VNode* _begin=allNode[_arc->begin->tag];
            VNode* _end  =allNode[_arc->end->tag];
            /*init data*/
            _arc->setBegin(_begin);
            _arc->setEnd(_end);
            _arc->setWeight(_w);

        }
        /* copy self to graph-obj */
        int copyTo(graph & _obj)
        {
            VNode *_node;
            VArc *_arc;

            for(int i=0;i!=nodeNum;i++)
            {
                _node=allNode[i];
                _obj.allNode.push(new VNode(_node->key,_node->tag,_node->weight,_node->status));

            }
            for(int i=0;i!=arcNum;i++)
            {
                _arc=allArc[i];
                _obj.addArc(_arc->begin->key,_arc->end->key,_arc->key,_arc->weight);
            }
            return 1;
        }
        int copyFrom(graph & _obj)
        {
            _obj.copyTo(*this);
            return 1;
        }
        /* get value from rightObj */
        void operator = (graph& _rObj)
        {
            copyFrom(_rObj);
        }
        /* remove arc by tag */
        int removeArcTag(int _tag)
        {

            VArc* _arc=allArc[_tag];
            _arc->begin->removeOutTag(_tag);
            _arc->end->removeInTag(_tag);
            allArc.remove(_tag);
            for(int i=_tag;i!=arcNum;i++)
                --allArc[i]->tag;

            return 1;
        }
        /* remove arc by key */
        int removeArcKey(int _key)
        {
            VArc* _arc;

            /* search by key */

            for(int i=0;i!=arcNum;i++)
            {
                if(allArc[i]->key==_key)
                {
                    _arc=allArc[i];
                    removeArcTag(_arc->tag);
                    return 1;
                }
            }

            return 0;
        }
        /* remove node by tag*/
        int removeNodeTag(int _tag)
        {

            VNode* _node=allNode[_tag];

            /* remove all inArc */
            for(;0!=_node->inNum;)
            {

                removeArcTag(_node->inArc[0]->tag);
                //_node->inArc.remove(0);
            }
            /* remove all outArc */
            for(;0!=_node->outNum;)
            {

                removeArcTag(_node->outArc[0]->tag);
                //cout<<_node->outNum;
                //_node->outArc.remove(0);
            }
            /* remove itself*/
            allNode.remove(_tag);
            for(int i=_tag;i!=arcNum;i++)
                --allArc[i]->tag;
            return 1;
        }
        /* remove node by key*/
        int removeNodeKey(int _key)
        {

            VNode* _node;
            /* search by key */

            for(int i=0;i!=nodeNum;i++)
            {
                if(allNode[i]->key==_key)
                {
                    _node=allNode[i];

                    removeNodeTag(_node->tag);
                    return 1;
                }
            }

            return 0;
        }

        int isGoEPath(int _beginKey,VTypeE * _edges,int _num,int _pos,int _endKey,int _deep=-1,int _type=25)
        {

            _deep++;
            static int temp=0,result;
            if(_pos>=_num+1)
            {
                _deep--;
                return 0;
            }if(_deep==0)
                result=0;
            int _tag = findNodeTag(_beginKey);

            VNode * _node = allNode[_tag];


            for(int i=0;i!=_node->outArc.n;i++)
            {    

                if(_node->outArc[i]->weight.type!=_type)
                {
                    if((_node->outArc[i]->weight==_edges[_pos])==2)
                    {

                        if(_node->outArc[i]->end->key==_endKey&&_pos>=_num)
                        {
                            _deep--;
                            return 2;
                        }else if(_node->outArc[i]->end->key==_endKey)
                        {
                            _deep--;
                            return 1;
                        }
                        if(temp=isGoEPath(_node->outArc[i]->end->key,_edges,_num,_pos,_endKey,_deep))
                            if(_deep!=0)
                            {
                                _deep--;
                                return temp;
                            }else if(temp==2)
                            {
                                _deep--;
                                return temp;
                            }else
                                result=1;
                    }else if((_node->outArc[i]->weight==_edges[_pos])==1)
                    {

                        if(_node->outArc[i]->end->key==_endKey&&_pos>=_num)
                        {
                            _deep--;
                            return 2;
                        }else if(_node->outArc[i]->end->key==_endKey)
                        {
                            _deep--;
                            return 1;
                        }if(temp=isGoEPath(_node->outArc[i]->end->key,_edges,_num,_pos+1,_endKey,_deep))
                            if(_deep!=0)
                            {
                                _deep--;
                                return temp;
                            }else if(temp==2)
                            {
                                _deep--;
                                return temp;
                            }else
                                result=1;
                    }else
                    {
                        continue;
                    }
                }
            }
            for(int i=0;i!=_node->outArc.n;i++)
            {    

                if(_node->outArc[i]->weight.type==_type)
                {
                    if((_node->outArc[i]->weight==_edges[_pos])==2)
                    {

                        if(_node->outArc[i]->end->key==_endKey&&_pos>=_num)
                        {
                            _deep--;
                            return 2;
                        }else if(_node->outArc[i]->end->key==_endKey)
                        {
                            _deep--;
                            return 1;
                        }
                        if(temp=isGoEPath(_node->outArc[i]->end->key,_edges,_num,_pos,_endKey,_deep))
                            if(_deep!=0)
                            {
                                _deep--;
                                return temp;
                            }else if(temp==2)
                            {
                                _deep--;
                                return temp;
                            }else
                                result=1;
                    }else if((_node->outArc[i]->weight==_edges[_pos])==1)
                    {

                        if(_node->outArc[i]->end->key==_endKey&&_pos>=_num)
                        {
                            _deep--;
                            return 2;
                        }else if(_node->outArc[i]->end->key==_endKey)
                        {
                            _deep--;
                            return 1;
                        }if(temp=isGoEPath(_node->outArc[i]->end->key,_edges,_num,_pos+1,_endKey,_deep))
                            if(_deep!=0)
                            {
                                _deep--;
                                return temp;
                            }else if(temp==2)
                            {
                                _deep--;
                                return temp;
                            }else
                                result=1;
                    }else
                    {
                        continue;
                    }
                }
            }
            _deep--;
            if(result==1)
            {

                return 1;
            }
            return 0;

        }
        int free()
        {


            for(;0!=nodeNum;)
            {
                delete allNode.pop();

            }
            for(;0!=arcNum;)
            {

                delete allArc.pop();
            }

            return 1;
        }
        ~graph()
        {

            free();

        }

    };
};





#endif


一个Demo的代码:
/* init.h  */


#include "frame.h"


#include "conio.h"
#include "runtime.h"

#include "regex.h"
using simplex::Regex;
int cpp(){



    cout<<"【VGL::Regex()v.1.0】\n";

    while(1)
    {

        char buf[100],buf_2[500];
        int len;
        cout<<"Regex>>>";os::control::read(buf,len,'\n');
        cout<<"String>>>";os::control::read(buf_2,len,'\n');

        Regex re;
        re.parse(buf);
        
        cout<<endl;
        cout<<(re.match(buf_2)?"〖True〗":"〖False〗");
        cout<<endl<<endl;
    }  
    return 0;
}



其运行结果: