[종만북] 짝이 맞지 않는 괄호(BRACKETS2) (C++)

문제 출처 :

www.algospot.com/judge/problem/read/BRACKETS2

algospot.com :: BRACKETS2

문제 풀이 :

• stack을 처음 배우면 무조건 예제로 풀게 된다는 괄호 검사 문제이다.
• 이 문제는 사실 stack을 이용한 구현 문제라고 생각해도 될 정도로 시키는 대로 구현하면 된다.
• 다만, 몇가지 예외사항때문에 틀리는 경우가 많을 것이다.
  예를 들면 첫번째 문자로 닫는 괄호( ) ] } ) 가 나오는 경우,
  혹은 여는 괄호만 들어온 경우( '(((((' ) 이런 경우들에 대한 예외처리를 제대로 해준 다면 수월하게 풀 수 있는 문제이다.

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

using namespace std;

int main()
{
	int c = 0;
	string my_str;
	
	cin >> c;
	stack<int> s;

	for (int i = 0; i < c; i++)
	{
		stack<char> stk;
		bool isFalse = true;
		cin >> my_str;




		for (int j = 0; j < my_str.length(); j++)
		{
			if (my_str[j] == '(' || my_str[j] == '[' || my_str[j] == '{')
			{
				stk.push(my_str[j]);
			}
			else if (stk.empty() and (my_str[j] == ')' || my_str[j] == ']' || my_str[j] == '}'))
			{
				isFalse = false;
				break;
			}
			else
			{
				if (my_str[j] == ')')
				{
					if (stk.top() != '(')
					{
						isFalse = false;
						break;
					}
					else
					{
						stk.pop();
					}
				}
				else if (my_str[j] == ']')
				{
					if (stk.top() != '[')
					{
						isFalse = false;
						break;
					}
					else
					{
						stk.pop();
					}
				}
				else if (my_str[j] == '}')
				{
					if (stk.top() != '{')
					{
						isFalse = false;
						break;
					}
					else
					{
						stk.pop();
					}
				}
			}
		}
		if (!stk.empty()) isFalse = false;

		if (isFalse)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}

	return 0;
}

• 종만북으로 공부하다보면 확실히 직관적이고 깔끔하게 (가끔은 너무 깔끔해서 어려운;;) 짜여진 코드를 볼 수 있는데 이 문제는 내가 짠 코드에 비하면 저엉말 깔끔하고 잘 짯다고 생각해서 코드를 보고 다시 짜보았다. string 의 .find를 쓰는 방법이 참 재밋는 방법이라는 생각이 든다.

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

using namespace std;

bool wellMatched(const string& formula)
{
	const string opening("([{"), closing(")]}");

	stack <char> openStack;

	for (int i = 0; i < formula.size(); i++)
	{
		if (opening.find(formula[i]) != -1)
			openStack.push(formula[i]);
		else {
			if (openStack.empty()) return false;

			if (opening.find(openStack.top()) != closing.find(formula[i])) return false;

			openStack.pop();
		}
	}
	return openStack.empty();
}

int main()
{
	int c = 0;
	string my_str;
	cin >> c;
    
	for (int j = 0; j < c; j++)
	{
		cin >> my_str;
		if (wellMatched(my_str))
		{
			cout << "YES\n";
		}
		else
		{
			cout << "NO\n";
		}
	}
	return 0;
}