我有一长串n(~50000)行,其中的公式如下:

A(1, 2) = 54353
A(1, 2, 3) = 89327
A(1, B(1, 2)) = 8372
A(7, B(1, 3, 5)) = 6311
A(7, B(C(1, 3, 7), 2, C(1, 3), 5)) = 28490
B(A(1, C(5, 3)), 3, 8, D(1, 2)) = 39783

等。
这些公式包含文字(即1235A(x, y)等)和函数调用(即A(x, y, z)B(x, y)A),其中函数的参数也可以是文字或其他(嵌套)函数调用函数(即BC*等)是固定的,并且没有太多函数(可能有十几个)。
现在我已经运行了带有完整公式或带有的模式的查询,这些模式应该充当glob字符,即:
A(1, 2) => [54353]
A(1, *) => [54353, 89327, 8372]
A(*, 3) => [89327]
A(*, B(*)) => [8372, 6311, 28490]
A(*, B(*, 3, *)) => [6311]

基本上,我有两个问题:
怎么做:事实上,我不知道一个好的基本模式匹配算法在这里我尝试过将带*的表达式转换为正则表达式,它适用于简单的示例,但是对于更复杂的示例,它失败了,例如:
Converting:
'A(*, B(*, 3, *))' => /^A\(.*, B\(.*, 3, .*\)\)$/

True positive:
'A(7, B(1, 3, 5))' =~ /^A\(.*, B\(.*, 3, .*\)\)$/

False positive:
'A(7, B(C(1, 3, 7), 2, C(1, 3), 5))' =~ /^A\(.*, B\(.*, 3, .*\)\)$/

我觉得将这些大括号表达式转换为反向波兰符号,然后应用常规正则表达式方法可能会有帮助,但我不确定。
如何快速完成:任何比为每个查询执行大约50000个匹配更快的想法都是非常受欢迎的。有可能在这里使用某种FSM吗?

最佳答案

正则表达式最初是为Regular Languages设计的,而您描述的是Context Free Language
你的语言可以被一个确定性的Push-Down Automata解析。
这个想法类似于fsm,但除此之外,还有一个stack元素,可以push()pop()元素。
更改FSM中的状态也取决于堆栈的头部。

关于algorithm - 大括号表达式公式中的模式匹配,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14629140/

10-11 23:03
查看更多