У меня есть длинный список из 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) или A(x, y, z) или 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]
В общем, у меня два вопроса:
Как это сделать вообще: на самом деле я не знаю здесь хорошего базового алгоритма сопоставления с образцом. Я пытался преобразовать выражения с * в регулярные выражения, и это работает для простых примеров, но, увы, не работает для более сложных, то есть:
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?
