[ALGOSPOT] Mismatched Brackets (BRACKETS2)

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

algospot.com :: 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:

1. Every bracket has a corresponding pair. ( corresponds to ), [ corresponds to ], et cetera.
2. Every bracket pair is opened first, and closed later.
3. 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)

 

<예제 입력>

3

()()

({[}])

({}[(){}])

 

<예제 출력>

YES

NO

YES

 

stack을 사용하는 전형적인 문제이다.

전체 string을 쭉 돌면서 여는 괄호들을 모두 stack에 넣고, 닫는 괄호들이 나올 때마다 stack의 top을 확인하면 되는 문제이다.

 

이러한 과정을 그림으로 그려 설명하면 이해가 빠르지만 나중에 추가하는 걸로..

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        string s;
        cin>>s;
        stack<char> st;
        bool flag = true;
        int ans = 0;
        for(size_t i=0;i<s.length();i++)
        {
            if(s[i]=='(' || s[i]=='[' || s[i]=='{') st.push(s[i]);
            else if(st.empty()) flag = false;
            else if(st.top() == '(' && s[i] == ')') st.pop();
            else if(st.top() == '[' && s[i] == ']') st.pop();
            else if(st.top() == '{' && s[i] == '}') st.pop();
            else flag = false;
        }
        if(!st.empty()) flag = false;
        if(!flag) cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}