BOJ 9012 — Parentheses

BOJ #9012 problem: https://www.acmicpc.net/problem/9012

---

We'll solve the problem using the stack learned in [Algorithm] - Stack!

Problem solving

Reading the problem, a parenthesis string (PS) is a string composed only of '(' and ')'.

Among these, the ones input with the parentheses in a correct arrangement are called Valid PS, VPS.

For example,

input like "()" is a VPS,

input like "(()())" is a VPS, and

input like "(()" is not a VPS.

If the input parenthesis string is a valid parenthesis string (VPS), output "YES", otherwise "NO", one per line.

Solution process

I used the stack supported by the C++ STL.

When receiving a string like "(())":

[When an opening parenthesis comes in]

Push any value onto the created stack.

[When it's a closing parenthesis]

1. When there's an opening parenthesis inside the stack, pop.
2. When the stack is empty, return FALSE.

[When you've gone through the whole input string]

When parentheses remain inside the stack, return FALSE.

That's what I thought.

Code

See more

#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;
}

---

Original (Korean): tistory — published 2021-06-03, migrated to this blog. This translation was generated with the help of AI.