代码写完后应该是这个效果:控制台键入“./a.exe 'a(b|c)*d' acbcd<回车>”,可以看到控制台显示“True”。
大致流程:
- 判断参数个数,参数不够就给出提示。
- 分析正规式的正确性。合法字符是数字、英文字母大小写、下划线、左右小括号、竖线“|”和星号“*”。
- 用树结构存储正规式。
- 对于每个树节点,计算当前位置的字串是否符合当前节点的匹配规则。
- 显示结果,结束。
节点就四种:基本单词节点、闭包节点、连接节点和分支节点,用 struct node{int type; union{......};}; 这样的结构存储就行。连接节点和分支节点的存储结构相同。
enum/*节点类型*/{ ND_WORD, ND_CAT, ND_CLOSURE, ND_BRANCH }; struct word_node{ const char *str; int nchar; }; struct list_node{ struct node **pp;//指向一堆指针 int nitem; int nalloc; }; struct node{ int type; union{ struct word_node word; struct list_node list;//ND_CAT,ND_BRANCH节点用此结构 struct node *closure; }; };
树的构建过程就用递归下降的方法吧,比较直观。仔细想想正规式串的文法其实挺简单,大概是:<B>:=<C>,<B>:=<C>'|'<B>,<C>:=<Q><C>,<C>:=ε,<Q>:=<W>,<Q>:=<W> '*',<W>:=<L><W>,<W>:=ε,<L>:='a'|'b'|...'z'|'_'。B分支,C连接,Q闭包,W单词,L字母。
下面伪代码的作用是尝试构建对应于“连接操作”的树节点。其它节点的构造方式差不多,反正就是递归下降分析法,废话不多讲。
struct node *concat() {
if(!(t = closure()))//降到closure一级 return NULL; if(!canbe_firstof_simple(*cursor))
//后面没有可用内容就不新建连接节点了,直接把t返回就行 return t;
w ← 新建连接节点, goto err if failed; add t to w->list, goto err if failed; do{ if(!(t = closure())) goto err; add t to w->list, goto err if failed; }while(canbe_firstof_simple(*cursor)); return w; err: destroy node t and w; return NULL; }
下面的代码检查给定字符串是否和正规式匹配。执行之前cursor指向字符串开头。
test(struct node *x) { if(!x) return false; switch (x->type) { case ND_WORD: if(!memcmp(cursor, x->word.str, x->word.nchar)){ cursor += x->word.nchar; return true; } return false; case ND_CLOSURE: while(test(x->closure)); return true; case ND_CAT: for(int i = 0; i < x->list.nitem; i++) if(!test(x->list.pp[i])) return false; return true; case ND_BRANCH: for(int i = 0; i < x->list.nitem; i++) if(test(x->list.pp[i])) return true; return false; } return false; }
上层驱动的逻辑是:
match(str,pat) { if(!str) return false; cursor = pat; struct node *t = branch();//使用递归下降方法构建一棵树 if(*cursor != ENDMARK) { puts("wrong pattern");//分析完了但cursor没走到头 destroy_node(t); return false; } cursor = str; bool r = test(t) && *cursor == ENDMARK; destroy_node(t); return r; }
这就是整个思路啦。代码就不一一列举了,一是篇幅太长,二是真没必要。整个过程比较简单,代码量也不大,一会儿就写出来了(当然调试的时间看具体情况)。
标签:node,return,struct,练习,ND,cursor,给定,字符串,节点 From: https://www.cnblogs.com/tingzhouduruo/p/lxzzbds.html