2021-06-03 · 1분

BOJ 9012 — 括弧

algorithmboj

この記事は公開から2年以上経過しています。

BOJ #9012 問題：https://www.acmicpc.net/problem/9012

[アルゴリズム] - スタック（Stack）で学んだスタックを活用して問題を解決します！

問題解決

問題を読んでみると、括弧文字列（Parenthesis String, PS）は '('、')' だけで構成される文字列を指すそうです。

そのうち括弧の形が正しい構成で入力されているものを Valid PS、VPS と呼ぶそうです。

例えば

"()" のように入力されれば VPS で、

"(()())" のように入力されれば VPS で、

"(()" のように入力されれば VPS ではない、というわけです。

入力された括弧文字列が正しい括弧文字列（VPS）なら "YES"、そうでなければ "NO" を 1 行に 1 つずつ出力すればよいです。

解法の過程

C++ STL で提供される stack を使った。

文字列を "(())" のように入力受け取ったとして

[開き括弧が入ってきたとき]

生成した stack に何でもよいので値を push する。

[閉じ括弧のとき]

スタック内部に開き括弧があるとき pop する。
スタックが empty のとき FALSE で返す。

[入力された文字列を全部回ったとき]

stack 内部に括弧が残っているとき FALSE で返す。

と考えた。

コード

#include <cstdio>
#include <stack>

#define TRUE 1
#define FALSE 0
#define COUNT 50

using namespace std;

stack<int> Stack;

int isVPS(char * str)
{
    for (int i = 0; str[i]; i++)
    {
        if(str[i] == '(') Stack.push(1);
        if(Stack.empty()) return FALSE;
        else if(str[i] == ')') Stack.pop();
    }
    if(Stack.empty()) return TRUE;
    return 0;
}

int main() {
    char insert[COUNT];
    int n, m, num;

    scanf("%d", &n);
    fgetc(stdin);

    for (int i = 0; i < n; i++)
    {
        
        while(!Stack.empty()) Stack.pop();
        scanf("%s", insert);
        fgetc(stdin);

        if(isVPS(insert) == FALSE) printf("NO\n");
        else printf("YES\n");
    }

    return 0;
}