[Algospot] 알고스팟 짝이 맞지 않는 괄호 문제풀이

괄호맞추기 - 전형적인 스택 이용해서 푸는 문제로, 개념은 쉽게 이해했으나 구현하면서 런타임오류가 많이 떴음(스택이 비었는데 계속 top을 찾거나, 변수이름을 비슷하게 설정해서 혼동한 부분도 있었음)

 

#include<iostream>
#include<string>
#include<stack>
using namespace std;
 
/*
문제 : 괄호 짝 맞추기 - (, {, [ 존재하고, 서로 교차할수 없으며, 먼저 열리고 닫혀야 함
시간제한 1초, 메모리제한 65535kb
 
<입력>
C        -> 테스트케이스
한 줄에 괄호들 모음 입력(10000글자 이하)
 
<출력>
괄호가 알맞으면 YES, 아니면 NO 출력
 
*/
stack<char> stacks;    //스택 생성
stack<char> stacks2;    //쌓아가는 스택
bool Go(char test) {    //괄호풀이 진행(가능하면 true, 아니면 false) - test : 이전에 나온 괄호모양
 
    while (!stacks.empty()) {
 
        stacks.pop();
        if (stacks.empty()) {    //마지막 test가 닫는괄호면 알맞을 수 없음
            if ((test == ')') || (test == '}') || (test == ']')) return false;
            if (stacks2.empty()) return false;    //비교할 stacks2가 없으면 끝
            if ((test == '(' && stacks2.top() == ')') || (test == '{' && stacks2.top() == '}') || (test == '[' && stacks2.top() == ']')) {
                //괄호 맞아 떨어짐
                stacks2.pop(); return stacks2.empty();
            }
            else return false;
        }
        if ((test == ')') && (stacks.top() == '(') || (test == '}') && (stacks.top() == '{') || (test == ']') && (stacks.top() == '[')) {
            //괄호가 맞아 떨어지는 경우
            stacks.pop();
        }
        else if ((test == '(') || (test == '{') || (test == '[')) {   //test가 여는 괄호인 경우 ->  stacks2와 비교
            if (stacks2.empty()) return false;
            if ((test == '(') && (stacks2.top() == ')') || (test == '{') && (stacks2.top() == '}') || (test == '[') && (stacks2.top() == ']')) {
                //stacks2랑, test가 맞아 떨어지는 경우
                stacks2.pop();
            }
        }
        else if ((stacks.top() == ')') || (stacks.top() == '}') || (stacks.top() == ']')) {
            //괄호가 안맞아떨어지지만, 더 봐야하는 경우
            stacks2.push(test);
 
        }
        else return false;    //괄호가 알맞지 않은 경우
        if (stacks.empty() && stacks2.empty()) return true;
        else if (stacks.empty() && !stacks2.empty()) return false;
        test = stacks.top();
    }
    return true;
}
 
int main() {
    int C; cin >> C;
    while(C--) {    //testcase
        
        while (!stacks.empty()) stacks.pop();
        while (!stacks2.empty()) stacks2.pop();
        
        string a; cin >> a;        //\n빼고 입력받음
        for (int i = 0; i < a.size(); i++) //스택에 다 집어넣음
            stacks.push(a[i]);
        
        bool answer = Go(stacks.top());
        if (answer) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}