[알고리즘] Day1 - 괄호

01 문제

02 알고리즘

• 입력된 문자열을 스택에 push, pop 하면서 괄호의 짝이 맞는지 확인한다.
  
• 문자열에서 ‘(‘ 일 때 push한 횟수와 ‘)’일 때 pop한 횟수가 같아야 한다.
  
• is_empty 함수를 이용해 push한 게 다 pop 되었는지 비교하는데,  pop을 더  많이 하는 경우도 고려해주어야 하므로 stack에서 pop할 요소가 없을  경우에 vps = -1로 해주고, 이 값이 초기값과 같은지 비교함.

03 코드

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define LEN 100

 

typedef struct array_stack

{

        int arr[LEN];

        int top;

}array_stack;

 

void stack_init(array_stack *pstack);

void push(array_stack *pstack, int x);

void pop(array_stack *pstack);

void size(array_stack *pstack);

int is_empty(array_stack *pstack);

void top(array_stack *pstack);

int vps;

 

int main(void)

{

        int i, size, num;

        char str[50];

        array_stack stack;

 

        scanf("%d", &num);

        getchar();

 

        while (num--)

        {

                 scanf("%s", str);

                 size = strlen(str);

                 stack_init(&stack);

                 for (i = 0; i < size; i++)

                 {

                         if (str[i] == '(')

                                 push(&stack, i);

                         else if (str[i] == ')')

                                 pop(&stack);

                 }

                 if (is_empty(&stack) == 1 && vps == 0)

                         printf("YES\n");

                 else

                         printf("NO\n");

        }

}

void stack_init(array_stack *pstack)

{

        vps = 0;

        pstack->top = -1;

}

void push(array_stack *pstack, int x)

{

//      vps = 0;

        ++pstack->top;

        pstack->arr[pstack->top] = x;

}

void pop(array_stack *pstack)

{

        if (pstack->top == -1)

                 vps = -1;

        else

                 pstack->top--;

}

void size(array_stack *pstack)

{

        printf("%d\n", pstack->top + 1);

}

int is_empty(array_stack *pstack)

{

        if (pstack->top == -1)

                 return 1;

        else

                 return 0;

}

void top(array_stack *pstack)

{

        if (pstack->top == -1)

                 printf("-1\n");

        else

                 printf("%d\n", pstack->arr[pstack->top]);

}