[자료구조] stack을 활용한 괄호쌍 짝짓기

1. 괄호쌍의 유효성

괄호쌍의 유효성이란 열린괄호' ( '와 닫힌 괄호' ) '가 서로 순서와 짝이 맞게 이루어져있는지 판단해주는 방법이다.

일반적으로 괄호쌍을 다룰 때에 소괄호' ( '가 주로 판단대상이지만 중괄호' { '나 대괄호' [ '로 확장하여 판단하기도 한다.

 

• 괄호쌍이 유효한 경우
  ( )
  ( ( ) )
  ( [ ] )
• 괄호쌍이 유효하지 않은 경우
  ) (
  { ( } )
  { } )

2. stack을 이용한 괄호쌍 유효성 검사하기

알고리즘

그러면 어떻게 이를 판단할 수 있을까?

 

위에서 괄호쌍이 유요하지 않은 경우는 괄호의 짝이나 순서 또는 개수가 맞지 않는다는 것을 확인할 수 있다.

데이터가 입력되었을 때 현재까지 입력된 상태를 유지하고 제일 마지막에 입력된 값과 비교해야 함을 느낄 수 있다.

 

따라서 자료구조의 stack을 이용하면 매우 유용하게 괄호쌍의 유효성을 검사할 수 있다.

 

문자열을 탐색하며 열린 괄호( ' ( ' 또는  ' [  ' )가 닫힌 괄호( ' ) ' 또는  ' ]  ' )와 만날 때마다 짝을 지어서 준다. 이 과정에서 자료구조의 스택(stack)을 이용하여 데이터를 넣고 제거해준다. 알고리즘의 순서는 다음과 같다.

 

1. 열린 괄호( ' ( ' 또는  ' [  ' )가 나오면 stack에 차례대로 추가한다.
   
2. 닫힌 괄호( ' ) ' 또는  ' ]  ' ) 가 입력될 경우 비교를 위해 stack이 비어있으면 추가하고 stack의 top과 비교하여 쌍이 맞을 경우에 stack에서 제거한다.
3. 1회의 탐색 후 stack이 비어있으면 모두 쌍이 맞아서 사라진 것이고, stack이 비어있지 않으면 쌍이 맞지 않은 경우이다.

---

예시

다음의 입력 예시를 통해 stack에서 괄호가 추가되고, 제거되는 과정을 보면 다음과 같다.

입력1: [   (   [   ]   )   ]

입력2: [   (   ]   )

 

위의 알고리즘을 실행하면 입력1의 경우 stack은 다음과 같다.

1) ' [ ' 추가
→ stack:  [ 

2) ' ( ' 추가
→ stack:  [   (

3) ' [ ' 추가
→ stack:  [   (   [

4) 괄호 쌍 확인 후 ' [ ' 제거하기
→ stack:  [   (   [   ]  괄호쌍 확인 후 짝이 맞으므로 제거 → stack:   [   (

5) 괄호 쌍 확인 후 ' ( ' 제거하기
→ stack:  [   (   ) 괄호쌍 확인 후 짝이 맞으므로 제거 →  stack:   [ 

6) 괄호 쌍 확인 후 ' ( ' 제거하기
→ stack:  [   ] 괄호쌍 확인 후 짝이 맞으므로 제거 →  stack:   empty

 

입력2의 경우는 다음과 같다.

1) ' [ ' 추가
→ stack:   [ 
2) ' ( ' 추가
→ stack:   [   (

3) 괄호쌍 확인 후 짝이 맞지 않으므로 stack유지
→ stack:  [   (   ] 괄호 쌍 확인 후 짝이 맞지 않으므로 유지 → stack:  [   (

4) 괄호쌍 확인 후 짝이 맞지 않으므로 stack유지
→ stack:  [   (   ] 괄호 쌍 확인 후 짝이 맞지 않으므로 유지 → stack:  [   (

 

따라서 경우1은 짝이 맞으므로 탐색 후 stack이 비어있게 되고 경우2는 짝이 맞지 않으므로 탐색 후 stack이 차있다.

 

3. 알고리즘 구현하기

#define CASE1(x) ((x == '(') || (x == '['))
#define CASE2(x) ((x == ')') || (x == ']'))
#define CASE3(x, y) ((x == ']') && (y == '[') || (x == ')') && (y == '('))

#include<iostream>
#include<string>
#include<stack>

using namespace std;

stack<char> sta;
string str;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while (1) {
		getline(cin, str);
		if (str == ".") break;
		int index = 0;
		while (str[index] != '.') {
			if (CASE1(str[index])) sta.push(str[index]);
			if (CASE2(str[index])) {
				if (sta.empty()) sta.push(str[index]);
				if (CASE3(str[index], sta.top())) sta.pop();
				else sta.push(str[index]);
			}
			index++;
		}
		if (sta.empty()) cout << "yes\n";
		else cout << "no\n";
		while (!sta.empty()) {
			sta.pop();
		}
	}
	return 0;
}

 

4. 예제

예제로 풀어보면 좋은 문제들이다.

 

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상