<백준 알고리즘>9012번

스택을 응용하는 문제이다.

준비물:

1.Stack 자료구조.

2.string을 담을 배열.

원리.

1.'(' 문자열은 push, ')'문자열은 pop하여 문자의 끝이 도달했을때 스택에 남는것이 있으면 올바른 괄호 문자열(Valid PS, VPS)이 아님.

2.stack에 원소가 없는데 pop을 하면 올바른 괄호 문자열(Valid PS, VPS)이 아님.

이러한 성질을 이용하여 풀어보겠다.

아래는 코드이다.

#include<iostream>
#include<vector>
#include<string>
using namespace std;
template<class T>
class Stack
{
public:
	Stack()
	{
		lastIndex = 0;
	}
	static const int EMPTY_RETURN_CODE = -1;
	void Clear()
	{
		_stack.clear();
		lastIndex = 0;
	}
	void Push(const T& t)
	{
		_stack.push_back(t);
		lastIndex++;
	}
	T Pop()
	{
		if (!Empty())
		{
			int val = Top();
			_stack.pop_back();
			lastIndex--;
			return val;
		}
		else
		{
			return -1;
		}
	}
	int Size()
	{
		return _stack.size();
	}
	bool Empty()
	{
		return _stack.size() > 0 ? false : true;
	}
	int Top()
	{
		if (Empty())
			return -1;
		else
			return _stack[lastIndex - 1];
	}
protected:
private:
	vector<T> _stack;
	int lastIndex;
};
int main()
{
	int testCase = 0;
	cin >> testCase;
	cin.clear();
	vector<string> arrOfVPS;
	string tmpString;
	for (int i = 0; i < testCase; ++i)
	{
		cin >> tmpString;
		arrOfVPS.push_back(tmpString);
	}
	bool isVPS;
	Stack<char> tmpStack;
	for (auto str : arrOfVPS)
	{
		isVPS = true;
		tmpStack.Clear();
		for (int i = 0; i < str.size(); ++i)
		{
			if (str[i] == '(')
			{
				tmpStack.Push('(');
				//push
			}
			else
			{
				if (!tmpStack.Empty())
				{
					tmpStack.Pop();
				}
				else
				{
					isVPS = false;
					break;
				}
			}
		}
		if (isVPS && tmpStack.Size() == 0)
		{
			cout << "YES" << "\n";
		}
		else
		{
			cout << "NO" << "\n";
		}
	}
	return 0;
}