문제

https://www.acmicpc.net/problem/9012
괄호의 모양이 올바르게 구성된 문자열인지 판단하는 문제이다.
괄호의 여닫음이 올바르게 되어있는지 판단해주면 된다.

풀이

Stack 자료구조를 활용할 수 있다.
괄호로 이루어진 문자열을 순서대로 읽으며 ( 을 만났을 때 push 하고 ) 을 만났을 때 pop 을 해주자!
즉 ) 을 만났을 때 가장 최근에 연 괄호 ( 을 닫아주는 것이다. LIFO 성질을 가진 Stack 을 떠올릴 수 있을 것이다.

만일 ) 을 만났을 때 이미 Stack 의 사이즈가 0이라면 연 괄호가 없는 것이기 때문에 올바른 괄호 문자열이 될 수 없다.

문자열을 다 읽고 나서 Stack 의 사이즈가 0이 아니라면 이번에는 아직 열린괄호가 존재하는 것이기 때문에 올바른 괄호 문자열이 될 수 없다.

CODE

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
using namespace std;
#define endl '\n'
#define MAX 1e9

string isCorrect(string s) {
    stack<char> st;
    for(auto& ch : s) {
        if(ch == '(')st.push(ch);
        else {
            if(st.empty())return "NO";
            st.pop();
        }
    }
    
    return st.empty()
    ? "YES"
    : "NO";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    
    for(int i=0;i<n;++i) {
        string s;
        cin >> s;
        cout << isCorrect(s) << endl;
    }
    
    return 0;
}