[ALCOSPOT]非対かっこ

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

この問題はアルゴリズム問題解決策第2巻第19章から出ている.
この問題を解決した.
前学期の資料構造の授業で、スタックの章で勉強した計算機の問題を思い出した.
中位数法では,接尾辞法で式を変換する際にスタックを用いた.
中位数:(1+2*3)/4
接尾辞:1 2 3*+4/

括弧を多く見て、スタック

に入れます

個の被演算子に遭遇した後、式配列

に移行する.

演算子に遭遇したときにスタック

に入れる

がカッコを閉じると、スタックからカッコの上にあるすべての演算子を取り出し、数式配列の

に移動します.
上記のアルゴリズムを用いる、
この問題についてもあまり差がないと思います.
スケッチ


計画を立てるときは、配列には要素へのポインタが必要だと思います.
複文に直接スタックに入れて比較する必要はありません.
アルゴリズムは以下のようにまとめられている.
1.左かっこに遭遇したらスタックに入れる
2.右括弧に遭遇した場合、スタック上部の左括弧と比較する
-スタック内の左かっこを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;
}