올바른 괄호 판별 - 스택 활용

[(()){}{}] 와 같은 괄호가 있다.

이 괄호가 올바른지 확인하는 방법으로 스택을 사용한다.

여는 괄호는 스택에 그냥 넣어주면 된다.

닫는 괄호에서는 스택을 열어봐서 비교해봐야 한다.

 

현재 닫는 괄호가 ')'일 경우 스택의 맨 위 요소는 '(' 여야만 한다.

아니라면, 괄호 짝이 안 맞아 괄호를 닫을 수가 없다...

그래서 닫는 괄호가 나올 때마다 스택의 맨 위 요소가 짝이 맞는지 확인을 해주어야 한다.

짝이 맞다면 닫는 괄호를 push 하지 말고 스택의 맨 위(확인한 여는 괄호)를 pop 해준다.

 

이 과정을 문자 하나하나 돌면서 문자열 끝까지 한다.

괄호가 올바르다면 스택에는 아무것도 없어야 한다.

왜냐하면, 다들 짝을 맞춰 pop을 했을 테니

 

소스 코드

#include <iostream>
#include <stack>
using namespace std;
stack<char> s;
bool solve(string str)
{
	int idx = 0;
	while (idx < str.length())
	{
		char ch = str[idx];

		switch (ch) {
		case '(':
		case '[':
		case '{':
			s.push(ch);
			break;
		case ')':
		case ']':
		case '}':
			if (s.empty())
				return false;
			if (ch == ')' && s.top() != '('
				|| ch == ']' && s.top() != '['
				|| ch == '}' && s.top() != '{')
				return false;
			s.pop();
			break;
		}
		idx++;
	}
	if(!s.empty())
		return false;
	return true;
}
int main(void)
{
	cout<<solve("[{{}()}]");
}