[자료구조] 스택(stack)의 응용1 : 괄호검사 - 컴도리돌이

반응형

괄호 검사란?

괄호의 종류로는 대중소([,]), ({,}), ((,))가 있는데 3가지 조건이 성립해야 한다.

 

조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.

조건 2 : 동일 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

조건 3 : 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안 된다.

 

괄호 검사 예시

 

괄호 검사 성공

괄호 검사 실패

괄호 검사 알고리즘

괄호 검사 알고리즘

 

• 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 push()
• 오른쪽 괄호를 만나면 pop() 연산으로 스택의 top에 있는 괄호를 꺼냄

         - 꺼낼 수 있는 요소가 없으면 즉, 스택이 비어 있으면 조건 2에 위배

         - pop 한 왼쪽 괄호와 짝이 맞지 않으면 조건 3에 위배

• 마지막 괄호까지를 조사한 후에도 스택에 괄호가 남아 있으면 조건 1에 위배

 

괄호 검사 - c언어