JavaScript에서 부분 문자열의 동작에 문제가 있음

Question

정규 표현식을 구문 분석하여 유한 상태 자동 완성을 작성하는 재귀 알고리즘을 작성했습니다. 오토마타는 표현식을 반복하여 문자를 스택으로, 연산자를 "연산자 스택"으로 푸시합니다. "("(그룹화 연산을 나타냄)을 만났을 때 스택에 "sub automaton"를 푸시하고 패턴의 나머지 부분을 파싱 할 서브 자동화에 전달합니다.) 해당 오토 마톤이 ")"을 만날 때 나머지 파싱을 끝내기 위해 부모 오토 마톤까지의 문자열. 코드는 다음과 같습니다.

var NFA = function(par) { 
    this.stack = []; 
    this.op_stack = []; 
    this.parent = par; 

}; 

NFA.prototype.parse = function(pattern) { 
    var done = false; 
    for(var i in pattern) { 
    if (done === true) { 
     break; 
    } 
    switch(pattern.charAt(i)) { 
     case "(": 
     var sub_nfa = new NFA(this); 
     this.stack.push(sub_nfa); 
     sub_nfa.parse(pattern.substring(i+1, pattern.length)); 
     done = true; 
     break; 
     case ")": 
     if (this.parent !== null) { 
      var len = pattern.length; 
      /*TROUBLE SPOT*/ 
      this.parent.parse(pattern.substring(i, pattern.length)); 
      done = true; 
      break; 
     } 
     case "*": 
     this.op_stack.push(operator.KLEENE); 
     break; 
     case "|": 
     this.op_stack.push(operator.UNION); 
     break; 
     default: 
     if(this.stack.length > 0) { 
      //only push concat after we see at least one symbol 
      this.op_stack.push(operator.CONCAT);   
     } 
     this.stack.push(pattern.charAt(i)); 
    } 
    } 
}; 

"문제가있는 부분"이라고 표시된 부분에주의하십시오. 정규식 "(a | b) a"가 주어지면 this.parent.parse라는 호출은 정확히 한 번 호출됩니다. 즉, 하위 자동 장치가 ")"을 만날 때입니다. 이 시점에서, pattern.substring (i, pattern.length) = ") a". 이것은 "작동"하지만 부모 오토 마톤에 문자열을 전달하기 전에 "") 입력을 사용해야하므로 올바르지 않습니다. 그러나 this.parent.parse에 대한 호출을 변경하면 (pattern.substring (i + 1, pattern.length)) 구문 분석을 통해 빈 문자열이 전달됩니다. 코드를 단계별로 실행했지만이 동작을 설명 할 수 없습니다. 나는 누락 되었습니까?

Juan의 제안에 따라이 알고리즘을 사용하여 "(a | b) a"를 구문 분석하려고 할 때 문제를 보여주기 위해 jsfiddle을 사용했습니다. ")"의 경우 빈 div가 i 인덱스의 하위 문자열과 i + 1 인덱스의 하위 문자열 i에있는 하위 문자열에는 2 개의 문자가 있지만 i + 1에있는 하위 문자열은 빈 문자열입니다. 여기에 링크가 있습니다 : http://jsfiddle.net/XC6QM/1/

EDIT : charAt (i)를 사용하면 알고리즘의 동작이 변경되지 않는다는 사실을 반영하여이 질문을 편집했습니다.

Answer 1

실제 문제는 for in을 사용하여 문자열의 문자를 반복한다는 사실입니다. for in 루프를 사용하면 i은 문자열이되므로 i+1을 시도하면 문자열 연결이 수행됩니다.

당신이 당신의 반복을 변경하는 경우

는

for(var i=0; i < pattern.length; i++) { 

그런 다음 모든 스콧의 대답은 문제를 정확하게 확인하지만 난 (숫자로 인덱스를 변환) 그의 해결책은 좋지 않은 생각 http://jsfiddle.net/XC6QM/2/

잘 작동합니다. 당신은 that does not work in IE 7

switch(pattern[i]) { 

이

switch(pattern.charAt(i)) { 

Answer 2

내가 생각해야한다, 또한

, 당신은 문자열 내의 문자에 액세스하는 브래킷을 사용하지 않아야로 시작하는 숫자 인덱스와 루핑 더 낫다 이전 대답은 올바른 방향이었습니다. 그러나 나에게 나에게 하나 하나의 오류라고 생각합니다. 하위 문자열의 색인을 늘려서는 안됩니까? 부모 구문 분석에 ")"를 포함하지 않으시겠습니까?

그러나 Juan이 언급 한 오류로 인해 여전히 실패합니다. 이 테스트하는 빠른 임시 수정은 숫자로 i를 변환하는 것입니다 :

이

this.parent.parse(pattern.substring(+i + 1, pattern.length)); 

이 당신을 위해 그것을 할 수 있습니다. 그러나 아마도 문자열로 되돌아 가서 문자열에서 for-in 루프로 전환해야합니다. 그게 네 문제를 일으키는 것 같아.배열을 str.split('')으로 바꾸고 정수를 사용하여 루프를 만듭니다. 그러한 문제가 더 이상 발생하지 않을 것입니다.