Skip to content

Latest commit

 

History

History
58 lines (34 loc) · 1.99 KB

4.回溯法.md

File metadata and controls

58 lines (34 loc) · 1.99 KB
Raw

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

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

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

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

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

介绍

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

1. 常见的回溯形式

  • 贪婪量词

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

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

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

"12345".match(/(\d{1,3}?)(\d{1,3})/);
// 没有回溯的情况 ["1234", "1", "234", index: 0, input: "12345"]

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

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

"candy".match(/can|candy/); // ["can", index: 0, input: "candy"]

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

2. 本章小结

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

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

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

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