regex - 检测灵活的模式？

Question

我需要检测数据集中的灵活模式。例如这样的模式:

0{1},1{*},0{1}
(the number between { and } is how many times a number may occur)

这将匹配:

0,1,0
0,1,1,1,1,1,0

上面的还是比较简单的，下面是比较难的:

0{1},( 1{*} | 1{*},2{1},1{*} ),0{1}
(the | pipe character is a "or")

这将匹配:

0,1,0
0,1,1,1,1,1,0
0,1,2,1,0
0,1,1,1,1,1,2,1,0

我发现很难理解如何检测这些灵活的模式。

我的第一个想法是生成某种决策树，但当模式变得更加复杂时，这就变成了一项相当困难的任务，尤其是因为你必须在这样的树中倒退并将路径标记为“不工作”并尝试其他路线。

对于这类问题，是否有更好的解决方案？

[edit] 哎呀，我可能把我的问题简单化了，小数字 0、1、2 在我的例子中不是数字，而是具有许多属性的对象。我的模式定义将匹配这些对象属性中的一个或组合。

Answer 1

听起来您正在谈论构建正则表达式匹配器。每个正则表达式都可以表示为 DFA .这是解释 how 的链接.