大佬的话，学习正则表达式，是需要懂点匹配原理的。而聊到匹配原理，就说道了
回溯,那么什么是回溯呢？这是我们这一章要明白的问题。
- 什么是回溯？
- 没有回溯的匹配是什么？
- 有回溯的匹配
- 常见的回溯形式
要明白什么是回溯，那需要先看一个没有回溯的匹配是什么？就明白了
没有回溯的匹配
假如我们的正则是/ab{1,3}c/，它的可视化是：
image.png
{1,3}是量词，表示要匹配1到3次的b。
假如我们要匹配abbbc。
- 先从
a出发，正好第一个字符是a，匹配成功。 - 接着我们从第二个字符
b{1,3}.它要求字符是b，要1到3次。我们匹配到了第二个字符b - 上一个条件我们满足，我们继续往下走，看看是不是可以满足2次呢？我们匹配到了第三个字符
b - 居然又满足，是不是可以满足3次呢？我们匹配到了第四个字符
b. - 前面的正则都满足，那么我就开始匹配正则下面的要求了。是不是
c呢？ 居然真的是？？？我们匹配到了第五个字符c.
至此所有正则全都匹配，没有必要重头开始。所以没有回溯匹配。
动图是这样：
image.png
有回溯的匹配
知道了没有回溯的，那么有回溯的就好理解了吧！
例如我们要匹配abbc，中间就会有回溯。
image.png
在第五步的时候，我们想要匹配b{1,3}，是否满足它有3个字符时，发现它不是b而是c，那么就认为b{1,3}就已经匹配完毕。然后状态又回溯到之前的状态，也就是第六步和第四步一样。就是它回退了一步。你既然这个不满足，那么我就回退一步，重新走，看看回退一步是不是可以满足呢？
所以这里它回退了一步，从c开始出发，发现可以匹配。开心！
还可以看一个更直观的例子：
正则匹配/ab{1,3}bbc/，而我们要匹配的字符串是：abbbc。
加入我们要能匹配到abbbc这个字符串，那么我们的量词条件就不能满足3的次数，而只能是1的次数。
但是正则引擎不知道呀，它只能按个试了，我先从abbb来试，看看能不能走通呢？
结果发现走到ab{1,3}的时候就走不下去了，因为它要求后面还有两个b，怎么办呢？
只能回退一步，看看条件能走下去不？结构发现abb也不能，因为它要求后面还有两个b，
可是字符串不够了呀？算了，我再退一步，好吧！我要求ab后面跟着两个b可以不？
哎，可以。开心，后面是c，也可以，开心！
image.png
常见的回溯形式
正在表达式匹配字符串的这种方式，有一个学名，叫回溯法。
回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发
所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从
另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、 不断“回溯”寻找解的方法，就称作“回溯法”。 — 百度百科
1.贪婪量词
之前的例子中我们使用的就是贪婪量词来实现的。因为是贪婪的，所以会尽可能往多的方向去尝试，先尝试多的，{1,3}，看看是不是满足3个，如果是我就继续尝试，如果不满足，我就吐出来一个，还不能满足，我就再吐。
虽然局部是贪婪的，但是也要满足整体能正确匹配。要不，要你何用呢？
如果多个贪婪量词挨着会不会冲突呢？
答案是，先下手为强：
var string = "12345";
var regex = /(\d{1,3})(\d{1,3})/;
console.log( string.match(regex) );
// => ["12345", "123", "45", index: 0, input: "12345"]
2.惰性量词
贪婪量词有回溯，你不会以为惰性量词就没有把，是否有回溯其实取决于整体的匹配，知道你容易满足，一个就够了，但是为了大局着想，还是要多给你一点。
var string = "12345";
var regex = /(\d{1,3}?)(\d{1,3})/;
console.log( string.match(regex) );
// => ["1234", "1", "234", index: 0, input: "12345"]
image.png
image.png
知道你不贪、很知足，但是为了整体匹配成，没办法，也只能给你多塞点了。因此最后\d{1,3}? 匹配的字 符是 "12"，是两个数字，而不是一个。
3.分支结构
我们知道分支也是惰性的，比如 /can|candy/，去匹配字符串 "candy"，得到的结果是 "can"，因为分支会
一个一个尝试，如果前面的满足了，后面就不会再试验了。
分支结构，可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分
支。这种尝试也可以看成一种回溯。
image.png
目标字符串candy的匹配过程是：
image.png
总结
什么是回溯法呢？
简单总结就是，正因为有多种可能，所以要一个一个试。直到，要么到某一步时，整体匹配成功了；要么最 后都试完后，发现整体匹配不成功。
- 贪婪量词“试”的策略是：买衣服砍价。价钱太高了，便宜点，不行，再便宜点。
- 惰性量词“试”的策略是：卖东西加价。给少了，再多给点行不，还有点少啊，再给点。
- 分支结构“试”的策略是：货比三家。这家不行，换一家吧，还不行，再换。
网友评论