技海无涯:正则表达式相关的知识和技术(1)——表达式-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

技海无涯:正则表达式相关的知识和技术(1)——表达式

简介:

正则表达式,看似简单,实则博大精深。简简单单几个字符:|*、(、)……却能够演绎出无穷无尽的变化。初看正则表达式,其实就是一串子字符串,但隐藏在这字符串背后的各种各样的知识、技能、技巧,却一点也不简单。

以前在学习《编译原理(龙书)》的时候,也是一目十行的将其跳过,这次偶尔需要用到正则表达式,然后自己就上网搜了搜,结果发现水不是一般的深,耗费了3个晚上的时间搜索、查阅,才稍微理清了这些相关知识的关系和脉络,于是稍作整理归纳,既为了加深自己的理解,也为了共享给各位。

在正式开始之前,先将相关东东列出来,看看你能够知道几个?

NFA、逆波兰表达式、双栈、自动机、子集算法、中缀表达式、Thompson算法。

 

技海无涯:正则表达式相关的知识和技术

看到下面这一堆东东,你是不是觉得头皮发麻,思维混乱呢?

NFA、逆波兰表达式、双栈、自动机、子集算法、中缀表达式、Thompson算法……

按照这种散乱无章的顺序来理解和记忆,当然是感觉很混乱了。 其实事情没有那么复杂,要想理解起来容易,记忆也牢固,我们要抓住一条思维的线路,然后将这一堆的东东沿着思维的线路进行分门别类,下面就是我总结出来的正则表达式的思路:

表达式->转换算法->编程技巧->自动机

首先正则表达式是一个表达式,但这个表达式最终是要让计算机理解和应用,这个理解和应用就是自动机。从表达式到自动机需要经过转换算法,在实现转换算法的时候有一些编程技巧,这样就把正则表达式从表达式到自动机串起来了。

下面我们一一介绍,这里只介绍简单的概念和知识点以及关联关系,详细的研究还需要各位自己上网查了。

 

表达式

表达式有几个相关的概念:前缀表达式、中缀表达式、后缀表达式、波兰表达式、逆波兰表达式。

概念介绍

前缀、中缀、后缀表达式很好理解,就是操作符在操作数前面、中间、后面,对应的英文分别是prefix notation, infix notation, postfix notation,英文好的大侠可以到google上直接搜索英文,有很多详细的介绍(如果要看详细的介绍和分析,一定要看英文),这里就不详细介绍了。

l         前缀表达式prefix notation:操作符在操作数前面,例如3+4转化成前缀表达式就是+34

l         中缀表达式infix notation:操作符在操作数中间,例如3+4转化成中缀表达式就是3+4

l         后缀表达式postfix notation:操作符在操作数后面,例如3+4转化成后缀表达式就是34+

 

表达式对比

三种表达式各自的特点和作用是什么呢?其实说白了就是谁理解更容易的问题:

前缀表达式:不好意思,我还没有弄懂前缀表达式的作用,据说是在Lisp语言中用到,有可能是Lisp这种语言更好理解前缀表达式。

中缀表达式:人更好理解,从小到大四则运算我们都是这么用的,大家写正则表达式也是这么写的;

后缀表达式:计算机更好理解,没有括号,没有优先级,按照顺序计算即可。

正则表达式的书写、四则运算的书写,都是按照中缀表达式来写的,但实际在计算机处理的时候,是需要转换成后缀表达式来进行处理(当然也可以不完全转换成后缀表达式后再进行计算,可以边分析边计算,后面在讲编程技巧的时候会详细分析)。

 

波兰、逆波兰

介绍到这里,似乎表达式的格式都涵盖了,总不可能来个“上缀”或者“下缀”表达式吧?既然这样的话,相信你一定会有这样的疑问:

1)什么叫波兰表达式?什么叫逆波兰表达式?

2)和波兰有什么关系么?

其实答案很简单,波兰表达式就是前缀表达式,逆波兰表达式就是后缀表达式。至于为什么和波兰扯上关系,其实也很简单,就是因为波兰表达式是波兰的逻辑学家Jan Łukasiewicz发明的,就像大家熟悉的Microsoft的“匈牙利命名法”,其实就是一个匈牙利工程师提出来的一样。

 

至于为什么没有“中波兰”表达式,这个还没有研究,也许哪位大侠申请一下,从此可以多一个“中国表达式”:)

 

 

参考资料

http://en.wikipedia.org/wiki/Reverse_Polish_notation

http://en.wikipedia.org/wiki/Prefix_notation

 

 

========================未完待续==================================

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章