백준 9012번: 괄호 (C++)

문제 링크 : https://www.acmicpc.net/problem/9012

 

간단한 stack문제다.

 

<전체적, 핵심 알고리즘>

열린 괄호면 stack에 넣고 닫힌 괄호면 미리넣었던 열린괄호를 빼버린다.(쌍을 하나씩 제거하는 방식)

쌍이 서로 다 맞아서 모두 삭제가 되면 vps이다.

 

<예외 케이스>

- 닫힌 괄호가 나왔는데 스택이 비어있으면 vps가 아니다. (닫힌 괄호의 쌍이 없음.)

- 닫힌 괄호가 나왔는데 스택 top이 열린 괄호가 아니라면 vps가 아니다. (마찬가지)

- 쌍들을 모두 삭제 해주었는데 스택에  남아있는 괄호가 있다면 역시 vps가 아니다.

 

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

using namespace std;



bool is_vps(string str)  
{
	stack<char> s;
	for (int i = 0; i < str.size() ;i++)
	{
		char c = str[i];
		if (c == '(')s.push(c);
		else if (c == ')')
		{
			if (s.empty()||s.top()!='(')return false;  //닫힘 괄호랑 쌍인 열린 괄호가 없으면 vps아님
			else s.pop();
		}
	}
	if (!s.empty())return false;  //아직 남아있으면 vps아님

	return true; 
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int t = 0; t < n; t++)
	{
		string str;
		cin >> str;
		bool istrue=is_vps(str);  //vps인지 아닌지
		if (istrue)cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.