#9012 괄호

# 문제

# 입력 및 출력

# 풀이

스택을 사용해서 간단하게 풀 수 있음

(이 입력되면 push해서 넣어주고 )이 입력되면 pop해서 삭제해주면 됨

괄호의 짝이 안맞으면 NO를 출력하고 짝이 맞는 경우엔 YES 출력하도록 작성

* 스택이 빈 상태에서 pop하지 않도록 예외처리를 해줄것

* 스택을 clear하기 위해서 while(!s.empty()) s.pop(); 코드를 사용해도 되지만

  난 그냥 반복문 돌 때마다 스택을 새로 선언해서 사용했음(시간 복잡도 문제)

#include <iostream>
#include <stack>
using namespace std;

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		stack<int> s;
		string ps;
		int isVPS = 1;
		cin >> ps;
		for (int j = 0; j < ps.size(); j++) {
			if (ps[j] == '(') s.push(0);
			else {
				if (s.empty()) isVPS = 0;
				else s.pop();
			}
		}
		if (s.empty()) {
			if (isVPS) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
		else cout << "NO" << endl;
	}
}