스택 - 1. 짝이 맞지 않은 괄호

문제 : 짝이 맞지 않은 괄호 (난이도 : 下)

 

https://algospot.com/judge/problem/read/BRACKETS2

 

 분석

Stack의 구조인 LIFO(Last In First Out)를 안다면 쉽게 접근할 수 있는 문제이다.

짝이 맞는지 확인하는 함수 wellMatched()에서 짝을 맞추는 과정을 유의 깊게 봐보자.

(주석 참조)

 

 구현

bool wellMatched(const string& input)
{
	// opening과 closing의 문자 순서를 유심히 보자.
	// idx로 짝을 맞추기에 같은 순서로 선언됐다.
	const string opening("({["), closing(")}]");
	stack<char> openStack;
	for (int i = 0; i < input.size(); i++)
	{
		// find() 함수는 일치하는 idx를 반환한다.
		// 만약 일치하는 값이 없으면 string::npos를 반환한다.
		// npos는 -1 값이다.
		if (opening.find(input[i]) != -1)
		{
			openStack.push(input[i]);
		}
		else
		{
			if (openStack.empty()) return false;
			if (opening.find(openStack.top()) != closing.find(input[i]))
			{
				return false;
			}
			// 짝을 맞춘경우 pop
			openStack.pop();
		}
	}
	// 짝을 다 맞추고 스택이 비어야 성공
	return openStack.empty();
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		string input;
		cin >> input;
		if (wellMatched(input)) cout << "Yes" << '\n';
		else cout << "No" << '\n';
	}
	return 0;
}