BOJ 9012 괄호

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

9012번: 괄호

요약

'('와 ')'로 이루어진 괄호 문자열이 주어질 때, 괄호의 모양이 바르게 구성된 올바른 괄호 문자열을 판정하자.

 

풀이

스택 자료구조를 사용하자. 닫는 괄호를 만날 때까지는 스택에 여는 괄호를 모두 Push 해가면서 닫는 괄호를 만나게 되면 바로 앞에서 push 한 여는 괄호와 짝지어 Pop 하여 준다. 문자열을 끝까지 탐색했을 때 스택이 비어있으면 괄호 모양이 올바른 것이므로 'YES', 아니라면 'NO'를 출력한다.

 

코드

#include <iostream>
#include<string>
#include <stack>
using namespace std;
int n;
string str;
bool chk;
stack<char> pq;
int main() {
    cin >> n;
    while (n--) {
        while (!pq.empty())
            pq.pop();
        chk = true;
        cin >> str;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '(') {
                pq.push(str[i]);
            }
            else if (str[i] == ')') {
                if (pq.empty()) {
                    chk = false;
                    break;
                }
                pq.pop();
            }
        }
        if (pq.empty() && chk == 1)
            cout << "YES" << "\n";
        else
            cout << "NO" << "\n";
    }
    return 0;
}