스택 응용 5. 괄호 매칭

C/C++에서는 중괄호를 사용하여 소스 코드를 묶는다. 소스 코드에 여는 괄호가 두 번 나왔다면 닫는 괄호도 반드시 두 번 나와야 한다. 

실제로 이러한 문법 검증 작업은 컴파일에 의해 이루어지며 이를 위해 컴파일러는 스택을 사용한다. 

 

다음은 유사코드로 작성한 괄호의 매칭이다. 

Matched = TRUE; //매칭 상태를 표시하는 변수 초기화
while(index <String.Length && Matched)
{
	Character = String[index++];	//새로운 문자를 잀어서
    if(Character is '{' )	//여는 중괄호면
    	push('{'); 			//스택에 푸시
    elsee if(Character is '}')//닫는 중괄호면
    	if(Not StackIsEmpty)	//스택이 비어있지 않다면
        	Pop()			//여는 괄호 제거
        else
        {
        	Matched =False;
            Break;
       	}
}
return Matched;

 

이를 응용한 문제는 다음과 같다. 

2022.04.22 - [C++/백준] - 백준 9012 - 괄호