백준 9012번 괄호

백준 9012번 문제 : https://www.acmicpc.net/problem/9012

---

[알고리즘] - 스택(Stack)에서 배운 스택을 활용하여 문제를 해결할 것입니다!

 

문제 해결

문제를 읽어 보았을 때 괄호 문자열(Perenthesis String, PS)은 '(', ')'만으로 구성되어 있는 문자열을 말한다고 합니다.

그중 괄호의 모양이 올바른 구성으로 문자열이 입력되어 있는 것은 Valid PS, VPS라고 부른다고 하네요.

 

예를 들면

"()" 이런 식으로 입력되면 VPS이고,

"(()())" 이런 식으로 입력되면 VPS이고,

"(()" 이런 식으로 입력되면 VPS 가 아닌 거이다.

 

입력된 괄호 문자열이 올바른 괄호 문자열(VPS)이면 "YES"를 아니면 "NO"를 한 줄에 하나씩 출력하면 됩니다.

 

풀이 과정

c++ STL에서 지원해주는 stack을 사용하였다.

 

문자열을 "(())" 이런 식으로 입력받았다고 했을 때

 

[여는 괄호가 들어왔을 때]

생성한 stack에 아무 값이나 push 해준다.

 

[닫는 괄호 일 때]

1. 스택 내부에 여는 괄호가 있을 때 pop를 해준다.
2. 스택이 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;
}