[algospot] BRACKETS2

문제링크 입니다

🚀 [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.

영어로 되어 있네요 간단히 소개하자면 괄호들이 짝이 잘 맞는지 확인하는 프로그램을 작성합니다.

🔑 [풀이]

스택을 이용하여 간단하게 해결할 수 있는 문제입니다.
여는 괄호와 닫는 괄호를 미리 저장하여 여는괄호를 스택에 저장하고 해당 닫는 괄호가 여는괄호를 저장한 스택의 탑과 비교한다.
코드참조.

⌨️ 입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 C (1≤C≤50)가 주어집니다. 그 후 C줄에 각 하나의 문자열로 테스트 케이스가 주어집니다. 이 문자열은 공백 없이 “(){}[]”에 포함된 글자만 주어지며, 길이는 1이상 10000이하입니다.

🖥 출력

괄호 문자열이 짝이 잘 맞으면 “YES”를, 아니면 “NO”를 한줄에 출력합니다.

🖱 입력 예제

3
()()
({[}])
({}[(){}])

💻 출력 예제

YES
NO
YES

💎 전체 코드는 다음과 같습니다.

//
//  BRACKETS2.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/29.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>

using namespace std;
ifstream fin("BRACKETS2.txt");

bool wellMatched(const string& S){
    // 여는 괄호와 닫는 괄호를 사전에 저장해줌
    const string opening("({["), closing(")}]");
    // 이미 열린 괄호들을 저장하는 스택
    stack<char> openStack;
    for(int i=0; i<S.size(); i++){
        // 여는 괄호라면 스택에 저장한다.
        if(opening.find(S[i]) != -1) openStack.push(S[i]);
        // 아니라면 문자와 맞쳐본다.
        else{
            // 만약 비었으면 불가능
            if(openStack.empty()) return false;
            // 서로 짝이 맞지 않아도 불가능
            if(opening.find(openStack.top()) != closing.find(S[i])) return false;
            // 서로 짝이 맞다면 스택에서 제거
            openStack.pop();
        }
    }
    // 스택이 모두 비어야 성공.
    return openStack.empty();
}

int main(){
    int test_case;
    fin >> test_case;
    for(int test=0; test<test_case; test++){
        string S;
        fin >> S;
        if(wellMatched(S)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}