Algospot BRACKETS2

문제 링크입니다: https://algospot.com/judge/problem/read/BRACKETS2

괄호의 순서가 올바르게 작성되었는지 확인하는 문제였습니다.

스택을 이용하면 간단하게 풀 수 있는 문제이기 때문에 어렵지 않게 풀 수 있는 문제입니다.

#include <iostream>

#include <string>

#include <stack>

using namespace std;

 

bool wellMatched(const string &formula)

{

        //여는 괄호 문자들

        const string opening("({[");

        //닫는 괄호 문자들

        const string closing(")}]");

       

        stack<char> stk;

        for (int i = 0; i < formula.size(); i++)

        {

                 //여는 괄호이면 무조건 스택에 push

                 if (opening.find(formula[i]) != -1)

                         stk.push(formula[i]);

                 //그 외의 경우 스택 맨 위의 문자와 비교

                 else

                 {

                         //스택이 비어 있는 경우 실패

                         if (stk.empty())

                                 return false;

                         //서로 짝이 맞지 않아도 실패

                         if (opening.find(stk.top()) != closing.find(formula[i]))

                                 return false;

                         //짝을 맞춘 괄호는 스택에서 뺀다

                         stk.pop();

                 }

        }

        //닫히지 않은 괄호가 없어야 성공

        return stk.empty();

}

 

int main(void)

{

        int C;

        cin >> C;

 

        for (int i = 0; i < C; i++)

        {

                 string s;

                 cin >> s;

 

                 if (wellMatched(s))

                         cout << "YES" << endl;

                 else

                         cout << "NO" << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]