2021-06-03 · 1분

BOJ 9012 — 括号

algorithmboj

这篇文章发布已超过两年，内容可能已过时。

BOJ #9012 题目：https://www.acmicpc.net/problem/9012

我们将活用在 [算法] - 栈（Stack）学到的栈来解决问题！

问题解决

读题可知，括号串（Parenthesis String, PS）指仅由 '('、')' 构成的字符串。

其中括号形状排列正确地输入的，称为 Valid PS，即 VPS。

例如

像 "()" 这样输入是 VPS，

像 "(()())" 这样输入是 VPS，

像 "(()" 这样输入就不是 VPS。

如果输入的括号串是有效括号串（VPS），就输出 "YES"，否则输出 "NO"，每行一个。

解题过程

使用了 C++ STL 提供的 stack。

设以 "(())" 这样接收字符串

[遇到开括号时]

往创建的 stack 里 push 任意值。

[是闭括号时]

栈内部有开括号时执行 pop。
栈为 empty 时返回 FALSE。

[遍历完输入的字符串时]

栈内部还剩括号时返回 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;
}