Stack의 활용 - 문자열에 들어있는 괄호의 짝 검사

프로그램에서는 여러 가지 타입의 괄호들이 같은 타입으로 쌍으로 존재하여야 한다.

프로그램에서는 대괄호, 중괄호, 소괄호 등이 사용된다.

괄호의 검사 조건은 다음의 3가지 이다.

 

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

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

조건 3 : 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다.

 

에러의 종류를 살펴보자.

 { A[ ( i + 1 ) ] }                             <= 오류 없음.

 if ( ( i == 0 ) && ( j == 0 )                 <= 오류. 조건 1 위반

A[ ( i + 1 ] ) = 0;                             <= 오류. 조건 3 위반

 

괄호 사용의 오류를 검사하는데, 스택을 사용할 수 있다.

위의 괄호들을 자세히 보면 가장 가까운 거리에 있는 괄호들끼리 서로 쌍을 이루어야 함을 알 수 있다.

따라서, 왼쪽 괄호들을 만나면 스택에 삽입하다가 오른쪽 괄호들이 나오면 스택에서 가장 최근의 왼족 괄호를 꺼내어 타입을 맞추어보면 쉽게 괄호들의 오류를 검사할 수 있다.

 

알고리즘

괄호의 오류 여부를 조사하려면 먼저 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면

스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 맨 위의 괄호를 꺼낸 후 짝이 맞는지 검사한다.

이 때, 스택이 비어 있으면 조건1 또는 조건 2등을 위배하게 되고 괄호의 짝이 맞지 않으면

조건 3에 위배된다.

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

조건 1에 위배되므로 오류기 때문에, FALSE를 반환하고, 그렇지 않으면 성공이므로

TRUE를 반환한다.

 

알고리즘 의사코드

 

구현

 

 

프로그램 결과

 

 

아래는 헤더 파일 및 소스 파일

common.h

0.00MB

main.c

0.00MB

MyStack.c

0.00MB

MyStack.h

0.00MB