[백준 9012번-C++] 괄호

 

http://acmicpc.net/problem/9012

 

{코드}

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

int main()
{
    int n;
    string s, ans = "";
    stack<char> st;
    cin >> n;
    while (n--)
    {
        cin >> s;
        stack<char> st;
        for (const char &c : s)
        {
            if (c == '(')
            {
                st.push(c);
            }
            else
            {
                if (!st.empty())
                {
                    st.pop();
                }
                else
                {
                    st.push('(');
                    break;
                }
            }
        }
        if (!st.empty())
        {
            ans += "NO\n";
        }
        else
        {
            ans += "YES\n";
        }
    }
    cout << ans;
}

{설명}

이 문제는 왼쪽 괄호와 오른쪽 괄호가 서로 짝을 이루는데 (규칙 1) 무조건 왼쪽 괄호가 존재해야 오른쪽 괄호가 존재할 수 있다는 조건이 있다고 생각하면 됩니다.

그에 따라 (가 들어오면 스택에 추가하고 )가 들어오면 스택에서 (를 하나 빼면 됩니다.

이때, )가 들어왔는데 (가 스택에 없다면 이는 규칙 1에 위배되므로 NO를 출력하면 됩니다.         .....  ㄱ

규칙 1에 위배되지 않으면서 반복문을 빠져나왔을때 스택에 아무것도 남아있지 않다면 모든 괄호가 짝을 이루었으므로 YES를 출력하고 스택에 (가 남아있다면 NO를 출력한다.

*ㄱ에서 원래는 NO를 ans에 추가해야 하지만 코드의 편의성을 위해 스택에 (를 추가하고 바로 반복문을 나오면 같은 역할을 하기 때문에 위와 같이 하였습니다.