正则表达式(四)- 回溯法原理

内容包括:

没有回溯的匹配
有回溯的匹配
常见的回溯形式

1、没有回溯的匹配

2、有回溯的匹配

3、常见的回溯形式

正则表达式匹配字符串的这种方式,有个学名,叫回溯法。

回溯法也称试探法,它的基本思想是:从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,
当一条路走到“尽头”的时候(不能再前进),再后退一步或若干步,从另一种可能“状态”出发,继续搜索,直到所有的“路径”
(状态)都试探过。这种不断“前进”、不断“回溯”寻找解的方法,就称作回溯法。

3.1 贪婪量词

尝试可能的顺序是从多往少的方向去尝试。

3.2 惰性量词

惰性量词就是在贪婪量词后面加个问号。表示尽可能少的匹配。

3.3 分支结构

分支会一个一个尝试,如果前面的满足了,后面就不会再试验了。

分支结构,可能前面的子模式会形成了局部匹配,如果接下来表达式整体不匹配时,仍会继续尝试剩下的分
支。这种尝试也可以看成一种回溯。

原文地址:https://www.cnblogs.com/xsnow/p/11959417.html