패턴 매칭

Question

내가 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, 함수의 인수가 리터럴 또는 다른 (중첩 된) 함수 호출이 될 수있는 함수 호출 (즉, A(x, y) 또는 A(x, y, z) 또는 B(x, y))이 포함됩니다. 기능 (예 : A, B, C 등)은 고정되어 있으며 너무 많지 않습니다 (12 개 정도 될 수 있음). 지금은 전체 공식이나 * 몇 가지 패턴 중 하나에 쿼리를 실행 한

하는 글로브 문자, 즉 역할을한다고 :

1. 방법 : 기본적으로

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

   나는 이러한 중괄호 식의 변환은 다음 역 폴란드 표기법하고 있다고 생각 정상적인 정규 표현 방식을 적용하면 도움이 될지 모르겠지만 확실하지 않습니다.

2. 수행 방법 빠른 답변 : 모든 아이디어가 어떻게 모든 쿼리에 대해 ~ 50000 개의 일치를 수행하는 것보다 빠릅니다. 여기서 FSM을 사용할 수 있습니까? 당신이 Context Free Language을 설명하는 동안

Answer 1

정규 표현식은 Regular Languages (원래)을 위해 설계되었습니다.

귀하의 언어는 Deterministic Push-Down Automata에 의해 구문 분석이 가능합니다.

아이디어는 FSM과 비슷하지만 및 pop() 요소가 가능한 stack입니다.
FSM에서 상태를 변경하는 작업은 스택 헤드에 따라 다릅니다.