[알고리즘]Algospot_BRACKETS2

출처 : https://www.algospot.com/judge/problem/read/BRACKETS2

문제

Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas have problems: some of the brackets are mismatched! Since there are so many formulas in his paper, he decided to check their validity with a computer program.

The following kinds of brackets are included in Best White’s paper.

Round brackets are opened by a ( and closed by a ).
Curly brackets are opened by a { and closed by a }.
Square brackets are opened by a [ and closed by a ].
A formula is said well-matched when the following conditions are met:

Every bracket has a corresponding pair. ( corresponds to ), [ corresponds to ], et cetera.
Every bracket pair is opened first, and closed later.
No two pairs "cross" each other. For example, [(]) is not well-matched.
Write a program to help Best White by checking if each of his formulas is well-matched. To make the problem easier, everything other than brackets are removed from the formulas.

입력

The first line of the input will contain the number of test cases C (1≤C≤100). Each test is given in a single line as a character string. The strings will only include characters in "{}" (quotes for clarity). The length of the string will not exceed 10,000.

출력

For each test case, print a single line "YES" when the formula is well-matched; print "NO" otherwise. (quotes for clarity)

정답코드

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

bool bracket(string& sen)
{
    stack<char> st;

    for(int i=0; i < sen.size(); i++)
    {
        if(sen[i] == '(' || sen[i] == '{' || sen[i] == '[')
            st.push(sen[i]);
        
        else
        {
            if(st.empty())  return false;
            
            if(st.top()=='(' && sen[i]==')')
            {   
                st.pop();
                continue;
            }
            else if(st.top()=='{' && sen[i]=='}')
            {   
                st.pop();
                continue;
            }
            else if(st.top()=='[' && sen[i]==']')
            {   
                st.pop();
                continue;
            }

            return false;
        }
    }

    if(!st.empty()) return false;
    return true;
}



int main()
{
    FASTio;

    int t;
    string a;

    cin >> t;

    while(t--)
    {
        cin >> a;

        if(bracket(a))  cout << "YES" << endl;
        else    cout << "NO" << endl;
    }

    return 0;
}

풀이 및 사고과정

간단한 문제였지만 stack에 있는 원소와 문자열을 비교하는 중에 stack이 비어있어도 비교시도를 하려고 해서 런타임에러가 발생했었다. 조건문으로 비교대상이 없을 경우 함수가 바로 false를 뱉을 수 있게 추가했더니 정답처리가 되었다.