정규식 (JavaScript)를

Question

이것은 내가 지금까지 만든 정규 표현식입니다 (2+2) + (2+3*(2+3))

일치하는 내가 얻을 수 있습니다

(2+2) 그리고 (2+3*(2+3)

일치 항목 :

(2+2) 그리고 (2+3*(2+3))

어떻게 정규 표현식을 수정해야합니까?

Answer 1

부모가있는 표현식을 정규식으로 구문 분석 할 수 없습니다. 정규 표현식으로이를 수행 할 수 없다는 수학적 증거가 있습니다. 괄호 안의 표현식은 문맥없는 문법이므로 pushdown automata (스택 머신)에서 인식 할 수 있습니다.

어쨌든 N 개의 괄호보다 작은 임의의 표현식에서 임의의 유한 N을 사용할 수있는 정규식을 정의 할 수 있습니다 (표현식이 복잡해 지더라도). 괄호에 다른 임의의 수의 상위가 포함될 수 있음을 인정하면됩니다.

\(([^()]+(\([^)]+\)[^)]*)*)\)

그것은 다음과 같이 작동

1. \(([^()]+는 괄호없는 무엇이든에 의해 follwed 여는 괄호를 일치;
2. (\([^)]+\)[^)]*)* 선택적으로, 열린 괄호로 구성된 다른 그룹이있을 수 있으며, 그 안에 뭔가가 들어 있고 그 뒤에 일치하는 닫는 괄호가옵니다. 다른 괄호 안의 다른 문자가 나타날 수 있습니다. 이것은 임의의 시간만큼 반복 될 수 있습니다. 어쨌든 마침내
3. )\) 첫 번째 것과 일치하는 다른 닫힌 괄호가 있어야합니다.

중첩 깊이 3을 원할 경우, 지점 (2)에서 설명한 각 그룹에 중첩 된 괄호 그룹을 허용하면서 더 깊이 재귀해야합니다.

스택을 사용하면 상황이 훨씬 쉬워집니다. 예 :

foundMatches = []; 
mStack = []; 
start = RegExp("\\("); 
mid = RegExp("[^()]*[()]?"); 
idx = 0; 
while ((idx = input.search(start.substr(idx))) != -1) { 
    mStack.push(idx); 
    //Start a search 
    nidx = input.substr(idx + 1).search(mid); 
    while (nidx != -1 && idx + nidx < input.length) { 
     idx += nidx; 
     match = input.substr(idx).match(mid); 
     match = match[0].substr(-1); 
     if (match == "(") { 
      mStack.push(idx); 
     } else if (mStack.length == 1) { 
      break; 
     } 
     nidx = input.substr(idx + 1).search(mid); 
    } 
    //Check the result 
    if (nidx != -1 && idx + nidx < input.length) { 
     //idx+nidx is the index of the last ")" 
     idx += nidx; 
     //The stack contains the index of the first "(" 
     startIdx = mStack.pop(); 
     foundMatches.push(input.substr(startIdx, idx + 1 - startIdx)); 
    } 
    idx += 1; 
} 

Answer 2

어떨까요 당신은 어떻게 정규식의 도움없이 루프를 사용하여 그것을 분석합니까? 당신은 변수를 가지고 있습니다 (0으로 초기화) 지금까지 건너 얼마나 많은 오픈 괄호를 추적합니다 "수준"라고해야 할 것입니다

• : 다음은 하나의 간단한 방법입니다.
• 각 일치 항목 (예 : (2 + 2) 또는 (2 + 3 * (2 + 3)))을 포함하려면 문자열 버퍼가 필요합니다.

• 마지막으로 일치하는 내용을 읽는 것을 끝낼 때마다 버퍼의 내용을 덤프 할 수있는 곳이 필요합니다.

• 문자로 문자열을 읽는 동안 "(", 건너 뛸 때 1 씩 감소) "을 발견하면 레벨이 1 씩 증가합니다. 그런 다음 캐릭터를 버퍼에 넣습니다.

• 당신이 ")"을 만났을 때 레벨이 0이되면, 당신이 일치하는 것을 알게됩니다. 이 때 버퍼의 내용을 덤프하고 계속합니다.

이 방법에서는 입력 문자열에 "("이 항상 해당 ")"이있을 것이라고 가정합니다. 이 메서드는 임의의 수의 괄호를 처리합니다.