[ BOJ / C++ ] 7585번 : Brackets

[ BOJ ] 7585번 : Brackets

문제 : https://www.acmicpc.net/problem/7585

---

[  문제  ]

As a C/Java programmer, you will be used to dealing with brackets. For the purpose of this problem, we will consider three type of bracket, round (), square [] and curly {}. As you know, every opening bracket must have a corresponding closing bracket, and brackets must be correctly nested. 

This problem will give you some pieces of code. You have to check whether the brackets are legal or not. To keep things simple, there will be no brackets enclosed in quotes (which do not follow the standard rules, of course). New line characters have also been removed, so each line of input represents one piece of code to be checked.

 

C/Java 프로그래머라면 대괄호를 다루는 데 익숙할 것입니다. 

이 문제에서는 round(), square[], curly{}의 세 가지 유형의 대괄호를 살펴보겠습니다. 

아시다시피 모든 여는 대괄호는 그에 대응하는 닫는 대괄호를 가져야 하며, 대괄호는 올바르게 중첩되어야 합니다.

이 문제에서는 몇 가지 코드가 주어집니다. 대괄호가 올바른지 확인해야 합니다. 

문제를 단순화하기 위해 따옴표로 묶인 대괄호는 사용하지 않습니다(물론 표준 규칙을 따르지 않습니다). 

줄 바꿈 문자도 제거되었으므로, 각 입력 줄은 검사해야 할 코드 조각 하나를 나타냅니다.

[  입력  ]

Input will consist of a number of lines of text (code), each one containing no more than 250 characters. The last line of input will contain just # - this line should be ignored. Each piece of code must be checked for legal brackets, and its status reported.

 

입력은 여러 줄의 텍스트(코드)로 구성되며, 각 줄은 250자를 넘지 않습니다. 

마지막 줄에는 #만 포함되어야 하며, 이 줄은 무시해야 합니다. 

각 코드에 대해 괄호가 제대로 사용되었는지 확인하고 상태를 보고해야 합니다.

[  출력  ]

If a line of code contains no brackets, or if all brackets are correctly paired and nested, the output should be Legal on a line on its own. If there are any errors, the output should be Illegal on a line on its own. 

 

코드 줄에 대괄호가 없거나 모든 대괄호가 올바르게 쌍을 이루고 중첩되어 있는 경우, 출력은 해당 줄에 "Legal"로 표시되어야 합니다. 오류가 있는 경우, 출력은 해당 줄에 "Illegal"로 표시되어야 합니다.

---

[  문제 접근 및 풀이  ]

올바른 괄호를 검사하는 방법은 스택의 TOP이 자신의 짝이면 된다.

따라서 스택을 이용해 열린 순서를 순서에 맞추어 담고 닫힌 괄호가 들어왔을 때 맞는 짝이면

괄호 쌍을 지워 마지막 괄호까지 갔을 때 모든 괄호들이 스택에서 나갔다면 올바른 괄호열이며

중간에 짝이 맞지 않거나 마지막까지 열린 괄호가 스택에 존재하면 올바르지 않는 괄호열이다.

따라서 이를 TF 함수로 판단해 참거짓을 판단해 출력하였고 "#"이 들어올 경우 종료했다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
string S;
void Q_7585();
bool TF();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    Q_7585();
}
void Q_7585(){
    while(true){
        getline(cin,S);
        if(S=="#") return;
        if(TF()) cout<<"Legal\n";
        else cout<<"Illegal\n";
    }
}
bool TF(){
    stack<char> V;
    for(auto x:S){
        if(x=='(' || x=='{' || x=='[') V.push(x);
        else if(x==')'){
            if(V.empty() || V.top()!='(') return false;
            V.pop();
        }
        else if(x=='}'){
            if(V.empty() || V.top()!='{') return false;
            V.pop();
        }
        else if(x==']'){
            if(V.empty() || V.top()!='[') return false;
            V.pop();
        }
    }
    if(!V.empty()) return false;
    return true;
}

---