JS 브래킷 일치 문제

코드워즈에서 대괄호 매칭 문제를 풀었습니다.

질문

문자열에서 괄호 {}, [], () 세 개가 일치하는지 확인하려면 중첩 상황을 고려해야 합니다.

예:

validBraces("(){}[]")     // true 
validBraces("(}")         // false 
validBraces("[(])")       // false 
validBraces("([{}])")     // true

해결 방법

이 문제에는 두 가지 기본 상황만 있습니다. 하나는 병렬입니다. 즉, ()와 같은 중첩이 없습니다. []{}; 또 다른 상황은 {[()]}와 같은 중첩된 상황입니다. 첫 번째 상황은 상대적으로 간단하고 두 번째 상황은 더 어렵습니다. 중첩 문제에 대한 해결책은 가장 안쪽의 괄호 쌍을 먼저 일치시키는 것입니다. 이는 우리가 종종 내부에서 시작한다고 말합니다.

첫 번째 방법:

function validBraces(braces){
  while(/\(\)|\[\]|\{\}/g.test(braces)){
    braces = braces.replace(/\(\)|\[\]|\{\}/g,"")
  }
  return !braces.length;
}

이 방법에서는 괄호 쌍을 찾은 다음 인접한 괄호 쌍을 빈 문자열로 바꾸는, 즉 삭제합니다. 마지막으로 문자열의 길이가 0인지 확인합니다. 예, 이는 완전한 일치를 의미하고, 그렇지 않으면 더 작은 일치를 의미합니다.
사실 이런 기획은 전형적인 '내부 붕괴'다. {[()]}를 예로 들어보겠습니다. 이제 가장 안쪽의 ()만 쌍을 이루고 인접해 있습니다. ()가 빈 문자열로 대체되면 []는 쌍을 이루고 인접하게 됩니다. 빈 문자열로. 인접한 괄호 쌍이 더 이상 발견되지 않을 때까지 이 루프에서 검색이 계속됩니다.

두 번째 방법:

function validBraces(braces){
  let leftBraReg = /[\(\{\[]/, 
    // 栈
      stack = [],
      bracket, rightBracket
  braces = braces.split('')
  for(bracket of braces) {
    if(leftBraReg.test(bracket)) {
      stack.push(bracket)
    }
    else {
      switch (bracket) {
          case ')':
          rightBracket = stack.pop()
          if(rightBracket !=='(') {
              return false
          }
          break
        case ']':
          rightBracket = stack.pop()
          if(rightBracket !=='[') {
              return false
          }
          break
        case '}':
          rightBracket = stack.pop()
          if(rightBracket !=='{') {
              return false
          }
          break
      }
    }
  }
  return stack.length === 0 ? true : false
}

왼쪽 반 괄호 즉, (, [, { 등)을 오른쪽 반 괄호에 저장하는 방법입니다. 즉, ), ], }가 순회되면 스택은 팝 작업을 수행한 다음 팝된 왼쪽 반 괄호를 순회된 반 괄호와 일치시켜 일치하는 다른 반 괄호인지 확인합니다. 순회가 완료되면 스택의 길이가 0이면 일치하고, 그렇지 않으면 일치한다고 판단됩니다.
또한 {[()]}를 예로 들어 처음 세 항목, 즉 {, [, (순회 시 스택에 푸시됨)은 스택 상단의 '('와 비교됩니다. 스택에서 튀어나온 후 일치하는지 확인하세요. 다음 ]과 }는 동일합니다.

결론

이제는 데이터 구조와 정규 표현식이 매우 중요하다는 것을 점차 깨닫습니다(여기서의 솔루션은 별도로 사용됩니다). 일상 생활에서는 거의 사용되지 않지만 응용 시나리오가 함께 있을 때. , 당신은 데이터 구조와 정규 표현식의 힘을 발견하게 될 것입니다.