본문 바로가기

Programming/Algorithm

C++ 스택을 사용한 괄호 짝 맞추기(Balanced brackets)

반응형

괄호 짝 맞추기(Balanced brackets)는 여는 괄호와 닫는 괄호의 짝이 맞는지 확인하는 문제입니다.

가장 나중에 열렸던 괄호 타입이 가장 먼저 닫혀야 됩니다.

이런 특성은 스택(Stack) 자료형을 활용하면 쉽게 구현이 가능합니다.

여는 괄호는 모두 스택에 넣고 닫는 괄호가 나올 때 스택의 최상단(Top)에 위치한 여는 괄호와 비교합니다.

그리고 닫는 괄호가 나왔을 때 스택이 비어 있으면 잘못된 짝으로 구성된 것입니다.

모든 문자를 비교한 이후에 스택이 깔끔하게 비었으면 완전한 괄호 짝이 맞는 문자열이 됩니다.

전체적인 코드는 다음과 같습니다.

30줄 남짓의 코드로 쉽게 구현이 가능합니다.

추가로 브라켓을 추가해야 하는 경우 map 타입의 pairs에 여는 괄호와 닫는 괄호 쌍을 입력해주면 됩니다.

이것으로 스택을 활용한 괄호 짝 맞추기 문제가 해결됩니다.

반응형