2

我有一长串 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

等等

这些公式包含文字（即1, 2, 3,5等）和函数调用（即A(x, y)or A(x, y, z)or B(x, y)），其中函数的参数也可以是文字或其他（嵌套）函数调用。函数（即A、B、C等）是固定的，它们的数量不会太多（可能有十几个）。

*现在我已经使用完整的公式或某种应该充当全局字符的模式运行查询，即：

A(1, 2) => [54353]
A(1, *) => [54353, 89327, 8372]
A(*, 3) => [89327]
A(*, B(*)) => [8372, 6311, 28490]
A(*, B(*, 3, *)) => [6311]

基本上，我有两个问题：

  1. 怎么做：事实上，我不知道这里有一个好的基本模式匹配算法。我尝试将带有 * 的表达式转换为正则表达式，它适用于简单的示例，但唉，对于更复杂的示例来说失败了，即：

    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, .*\)\)$/

    我觉得将这些大括号表达式转换为反向波兰符号，然后应用正常的正则表达式方法可能会有所帮助，但我不确定。

  2. 如何快速完成：任何比为每个查询执行约 50000 次匹配更快的想法都非常受欢迎。是否可以在这里使用某种 FSM？

4

1 回答 1

2

正则表达式（最初）是为正则语言设计的，而您正在描述Context Free Language。

您的语言可以被 Deterministic Push-Down Automata解析。

这个想法类似于 FSM，但除此之外，您还有一个可以使用的堆栈push()和pop()元素。
更改 FSM 中的状态也取决于堆栈的头部。

于 2013-01-31T15:28:03.900 回答