gpt4 book ai didi

algorithm - 大括号表达式公式中的模式匹配

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:52:10 25 4
gpt4 key购买 nike

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

等等

这些公式包含文字(即 1235 等)和函数调用(即 A(x, y)A(x, y, z)B(x, y)),其中参数函数也可以是文字或其他(嵌套)函数调用。函数(即 ABC 等)是固定的,而且数量不多(可能大约有十几个)。

现在我已经使用完整公式或带有 * 的一些模式运行了查询,它应该充当 glob 字符,即:

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 吗?

最佳答案

正则表达式是为 Regular Languages 设计的(最初),当你描述一个 Context Free Language .

您的语言可由确定性 Push-Down Automata 解析.

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

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

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com