四、正则表达式回溯法原理

概念理解起来比较容易。
比如用 /ab{1,3}c/ 去匹配下面两个字符串。

  • 当匹配 abbbc，按顺序匹配，到了第 3 个 b 后，直接匹配 c，这样就没有回溯。

  • 当匹配 abbc，按顺序匹配，到了第 2 个 b 后，由于规则是 b{1,3} ，则会继续往下匹配，然后发现下一位是 c，于是回退到前一个位置，重新匹配，这就是回溯。

另外像 /".*"/ 来匹配 "abc"de 的话，就会有三个回溯情况，为了减少不必要的回溯，我们可以把正则修改为 /"[^"]*"/。

介绍

回溯法，也称试探法，本质上是深度优先探索算法，基本思路是：匹配过程中后退到之前某一步重新探索的过程。

1. 常见的回溯形式

  • 贪婪量词

多个贪婪量词挨着存在，并相互冲突时，会看匹配顺序，深度优先搜索：

  1. "12345".match(/(\d{1,3})(\d{1,3})/);
  2. //  ["12345", "123", "45", index: 0, input: "12345"]
  • 惰性量词

有时候会因为回溯，导致实际惰性量词匹配到的不是最少的数量：

  1. "12345".match(/(\d{1,3}?)(\d{1,3})/);
  2. // 没有回溯的情况 ["1234", "1", "234", index: 0, input: "12345"]
  4. "12345".match(/^\d{1,3}?\d{1,3}$/);
  5. // 有回溯的情况 ["12345", index: 0, input: "12345"]
  • 分支结构

分支机构，如果一个分支整体不匹配，会继续尝试剩下分支，也可以看成一种回溯。

  1. "candy".match(/can|candy/); // ["can", index: 0, input: "candy"]
  3. "candy".match(/^(?:can|candy)$/); // ["candy", index: 0, input: "candy"]

2. 本章小结

简单总结：一个个尝试，直到，要么后退某一步整体匹配成功，要么最后试完发现整体不匹配。

  • 贪婪量词：买衣服砍价，价格高了，便宜点，再便宜点。

  • 懒惰量词：卖衣服加价，价格低了，多给点，再多给点。

  • 分支结构：货比三家，一家不行换一家，不行再换。