首页 > 其他分享 >练习:判断字符串是否与给定的正规式匹配

练习:判断字符串是否与给定的正规式匹配

时间:2023-05-07 09:56:17浏览次数:43  
标签:node return struct 练习 ND cursor 给定 字符串 节点

代码写完后应该是这个效果:控制台键入“./a.exe 'a(b|c)*d' acbcd<回车>”,可以看到控制台显示“True”。

大致流程:

  1. 判断参数个数,参数不够就给出提示。
  2. 分析正规式的正确性。合法字符是数字、英文字母大小写、下划线、左右小括号、竖线“|”和星号“*”。
  3. 用树结构存储正规式。
  4. 对于每个树节点,计算当前位置的字串是否符合当前节点的匹配规则。
  5. 显示结果,结束。

节点就四种:基本单词节点、闭包节点、连接节点和分支节点,用 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

相关文章

  • golang模拟键盘输入字符串
    介绍仅供学习使用哈,不要用来开gua。代码仓库:https://github.com/GuoFlight/gkeybd(本人仓库,欢迎留言)注意事项只支持英文使用前请切换到英文输入法。因为本程序只支持英文(模拟的是按键,而不是传递字符串)。Mac中使用可能会报错需要用vendor,并将vendor/github.com/micmona......
  • PTA练习题
    复数类Complex有两个数据成员:a和b,分别代表复数的实部和虚部,并有若干构造函数和一个重载-(减号,用于计算两个复数的距离)的成员函数。要求设计一个函数模板template<classT>doubledist(Ta,Tb)对int,float,Complex或者其他类型的数据,返回两个数据的间距。以上类名和函数模......
  • 重复子字符串
    应用KMP算法最长相等前后缀不包含的子串就是最小重复子串。 len=s.size();如果len%(len-(next[len-1]))==0 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环 此图为-1,......
  • GaussDB(DWS)字符串处理函数返回错误结果集排查
    摘要:在使用字符串处理函数时,有时会出现非预期结果的场景。在排除使用问题后,应该从encoding和数据本身开始排查。本文分享自华为云社区《GaussDB(DWS)字符串处理函数返回错误结果集排查》,作者:-CHEN111-。在使用字符串处理函数时,有时会出现非预期结果的场景。在排除使用问题后,应......
  • 实现字符串的拼接---Java
    定义一个方法,把int数组中的数据按照指定的格式拼接成一个字符串返回调用此方法,并在控制台输出结果 例如: 数组为:int[]arr={1,2,3}; 执行后输出结果为:[1,2,3]packagestring.practice;/**实现字符串的拼接*定义一个方法,把int数组中的数据按照指定的格式拼接成一个字......
  • shell jq处理json字符串
    1.1工具介绍自己用shell处理json字符串的时候,开发输入格式的不通会导致解析字符串有问题,所以这里用到了jq工具jq是一款命令行下处理JSON数据的工具。其可以接受标准输入,命令管道或者文件中的JSON数据,经过一系列的过滤器(filters)和表达式的转后形成我们需要的数据结构并将......
  • Java中对比两个字符串的相似度
    Java中对比两个字符串的相似度的方法,以下整理了两个方式比对方法,同样的字符串不同的计算方式得到的结果也是不同的:packagetest;/***对比俩个字符串的相似度*@authorsanshi*/publicclassStrUtil{/***获取最长子串(参数顺序与字符串长短无关)......
  • 常用的截取字符串方法JS和Golang实现
    JS中截取字符串很简单,直接使用substr函数substr()方法可在字符串中截取从开始下标开始的指定数目的字符。下标是从0开始算例如:"21".substr(0,1)  返回2golang实现的substr//截取字符串,支持多字节字符//start:起始下标,负数从从尾部开始,最后一个为-1//length:截取长度,......
  • python练习-简单计算器
    #*_*coding:utf8*_*#简单计算器importtkinterfromfunctoolsimportpartial#按钮输入调用defget_input(entry1,argu):#从entry窗口展示中获取输入的内容input_data=entry1.get()#合法运算符:+-*/--**//+-#------------输入合法性判断的......
  • 提取最新的各国疫情数据中json字符串
    1.正则表达式提取json字符串:   -----------------------------------------------------------------初始数据-----------------------------------------------------------------try{window.fetchIndexMallList={"success":true,"errorCode":0,"result......