[ALGOSPOT] 짝이 맞지 않는 괄호

박민주·2021년 10월 2일
0
post-thumbnail

https://www.algospot.com/judge/problem/read/BRACKETS2

이 문제는 알고리즘 문제 해결 전략 2권의 19챕터에서 나오는 문제이다!

이 문제를 풀다보니
지난 학기 자료구조 시간에 스택 챕터에서 배웠던 계산기 문제가 떠올랐다

중위표기법에서 후위표기법으로 수식을 변환할 때 스택이 사용되었었다

중위표기법 : ( 1 + 2 * 3) / 4

후위표기법 : 1 2 3 * + 4 /

  1. 여는 괄호를 만나면 스택에 넣는다
  2. 피연산자를 만나면 수식 배열로 옮긴다
  3. 연산자를 만나면 스택에 넣는다
  4. 닫는 괄호를 만나면 스택에서 여는 괄호 위에 있는 연산자를 모두 꺼내어 수식 배열로 옮긴다

위와 같은 알고리즘으로 동작했는데,
이 문제에서도 비슷했다고 생각이 된다

스케치

계획을 세울 땐 배열에서 원소를 가리키는 포인터가 필요하다고 생각했는데,
그냥 반복문에서 바로바로 스택에 넣고 비교하고 하면 되는 거라 필요없었다

알고리즘을 정리해보면 다음과 같다
1. 여는 괄호를 만나면 스택에 넣는다
2. 닫는 괄호를 만나면 스택의 Top에 있는 여는 괄호와 비교한다
- 짝이 맞으면 스택에 있는 여는 괄호를 Pop
- 짝이 맞지 않으면 검사를 종료

또한 아래와 같은 예외처리가 필요했다
1. 여는 괄호만 있을 경우
- 배열의 끝까지 검사를 마쳤는데 스택에 연산자가 남아있는 경우가 된다
- pop 연산이 이루어지지 못했으므로 짝이 맞지 않아 NO를 반환한다

2. 닫는 괄호만 있을 경우
- 이번 검사 대상이 닫는 괄호이고, 스택이 비어있을 경우가 된다
- 여는 괄호보다 닫는 괄호가 먼저 나왔다는 의미가 되므로 NO를 반환한다

CODE

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define SIZE 3

bool IsOpenBracket(vector<char> & open, char target);
bool IsMatch(char open, char close);
bool SearchBracketCouple(string input, vector<char> open_bracket);

int main(void)
{
    vector<char> open_bracket = {'(', '{', '['};
    
    vector<string> inputs;
    int testcase = 0;
    cin>>testcase;
    for(int i=0; i<testcase; i++)
    {
        string temp;
        cin>>temp;
        inputs.push_back(temp);
    }

    for(int i=0; i<testcase; i++)
    {
        if(inputs[i].size() % 2 != 0)
        {
            cout<<"NO"<<endl;
            continue;
        }

        if(SearchBracketCouple(inputs[i], open_bracket))
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
            
    }

    return 0;
}

bool SearchBracketCouple(string input, vector<char> open_bracket)
{
     stack<char> open;
    // 1. string을 순회한다
    // 2. 여는 괄호이면 push
    // 3. 닫는 괄호이면 stack의 top과 비교
    // - 맞으면 여는 괄호 pop
    // - 틀리면 탐색 종료
    
    for(int i=0; i<input.size(); i++)
    {
        // cout<<input_1[i]<<endl;
        if(IsOpenBracket(open_bracket, input[i]))
        {
            open.push(input[i]);
        }
        else
        {
            if(!open.empty())
            {
                if(IsMatch(open.top(), input[i]))
                {
                    open.pop();
                }
                else
                {
                    return false;
                }
            }
            else
                return false; 
        }
    }

    if(open.empty()) // 여는 괄호만 있어서 stack이 비워지지 못하면 false
        return true;
    else
        return false;
}

bool IsOpenBracket(vector<char> & open, char target)
{
    for(int i=0; i<open.size(); i++)
    {
        if(target == open[i])
        {
            return true;
        }
    }
    return false;
}

bool IsMatch(char open, char close)
{
    if(open == '{' && close == '}' )
        return true;
    else if(open == '[' && close == ']')
        return true;
    else if(open == '(' && close == ')')
        return true;
    else
        return false;
}
profile
Game Programmer

0개의 댓글