밸런스 스택을 사용하여 문자열에서 대괄호가 닫혀 있는지 확인하십시오.

Question

사용자 입력 문자열에서 대괄호 집합이 닫혀 있는지 확인하는 프로그램을 작성하고 있지만 어떻게해야하는지 혼란 스럽습니다. 스택을 사용하여이를 수행하십시오.

제 아이디어는 괄호가있는 경우 스택에 추가 한 다음 닫는 괄호가 나타나면 스택에서 상위 두 개의 문자를 튀어 나오게하고 두 번째로 튀어 나온 문자가 첫 번째 문자와 일치하는지 (예 : 대괄호가 일치하고 여는 대괄호와 닫는 대괄호) 행이 균형을 이룹니다. 그러나, 나는 예를 들어, 그들에 여러 브래킷과 문자로 문자열을 작업 할 수 있어야합니다 :

wfsfs[{{{(s;dkls(dslkf)s;dlkf}]}]}}}sd 

내가 스택을 사용하여이 작업을하는 방법에 대한 정말 혼란 스러워요! 어떤 아이디어?

다음

는 기본적으로 지금까지 함께했다 코드이지만 여러 괄호

작동하지 않습니다

for (int i = 0; i < x.length(); i++){ 
     if (x.charAt(i) == '('){ 
      stack.push('('); 
      } 
     if (x.charAt(i) == '['){ 
      stack.push('('); 
      } 
     if (x.charAt(i) == '{'){ 
      stack.push('('); 
      } 
     if (x.charAt(i) == ')'){ 
      stack.pop(); 
      if (stack.empty()){ 
       return true; 
       } 
      if (stack.pop() != ')'){ 
       return true; 
       } 
      } 
     if (x.charAt(i) == ']'){ 
      stack.pop(); 
      if (stack.empty()){ 
       return true; 
       } 
      if (stack.pop() != ']'){ 
       return true; 
       } 
      } 
     if (x.charAt(i) == '}'){ 
      stack.pop(); 
      if (stack.empty()){ 
       return true; 
       } 
      if (stack.pop() != '}'){ 
       return true; 
       } 
      } 

    } 

    return false; 
} 


} 

편집 : "X"는 inputed 문장

Answer 1

그래서이다, 이건 내 생각이다 . 당신은 열린 브래킷을 스택에 밀어 넣을 수 있습니다 (그리고 당신이 열린 브래킷을 가지고있을 때만 밀기). 스택에 아무것도 없어 팝업 할 수없는 경우 테스트가 실패합니다. 끝까지 다가 가서 스택에 무언가가 있으면 테스트가 실패합니다.

페어링해야하는 경우 ({{} {} {}} 실패가 성공하지 못함) 힘들어 지지만, 다시 실패하면 다시 터지기 시작하면 추적 할 수 있습니다.

편집 : 3 가지 "괄호"중 하나 (기술적으로 괄호, 중괄호 및 괄호가 있음) 중 하나와 일치해야하는 경우 3 개의 다른 스택을 가질 수도 있고 맨 위의 "괄호" 스택에서 닫는 것과 일치합니다.

EDIT2 : 나는 문자열을

: 의사 코드 예제를 보여 "[[]]"문자열을 통해

스캔, 내 첫 번째 문자는 오픈 브라켓입니다 참조 [난에이 팝 내 스택, 내 스택 1 항목을 '['로 크게 만듭니다.

내 다음 문자는 오픈 브라켓, 그래서 내가 내 스택에이 개 항목이 의미뿐만 아니라 스택에이 팝업, '['와 '['

세 번째 문자는 폐쇄 브래킷입니다 . 스택 상단에있는 짝을 들여서 거기에있는 대괄호와 일치하는 것을 볼 수 있으므로 스택에서 열린 대괄호가 열리고 스택에 하나의 대괄호가 남습니다. [

내 네 번째 문자는 닫힌 브래킷. 스택 상단에있는 엿보기에서 스택에있는 대괄호와 일치하는지 확인합니다. 이 괄호를 내 스택에서 꺼내서 빈 스택을 남겨 둡니다.

내 문자열을 끝내겠습니다. 스택이 비어 있음을 확인합니다.

편집 3 : 대괄호가 다른 예입니다.

내가 문자열을 말해봐 "[{() {}}]"

내 첫 번째 문자 인 '['내가

내 두 번째 문자는 스택에 그것을 팝에 '{ '그래서 내 세번째 문자 인

스택에 터지에'('그래서 스택 상으로 튀어

내 제 cahracter은 A') '그래서 PEEK와 스택의 최상위를 확인 . 그것은 일치하는 괄호 '('내가 스택에서 그것을 팝업 이동합니다.

내 다섯 번째 문자가이 '{'내가 스택에 팝.

내 여섯 번째 문자가있다 '}이다 '그래서 내 스택 맨 꼭대기에서 들여다보고, 일치하는'{ '을보고 스택에서 튀어 나오게합니다.

제 7 번째 문자는'} '입니다. 그래서 제 스택의 상단에서 들여다 보면 일치하는 것을 볼 수 있습니다. '{'그래서 스택에서 꺼내 웁니다.

내 8 문자가 ']'이므로 스택 맨 위에서 들여다보고 일치하는 ']'이 표시되어 스택에서 꺼내집니다.

나는 내 문자열의 끝에 도달하고 아무 것도 내 스택에 남지 않았으므로 나는 좋다.