https://www.acmicpc.net/problem/9012
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
스택에 쓰이는 ADT들을 정의했다.
스택 생성 후 스택의 초기화를 담당하는 Stackinit함수, 스택의 Push연산을 하는 Push함수,Pop연산을 하는 Pop함수 등을
구현하였다.
#include <stdio.h>
#include <string.h>
#define True 1
#define False 0
typedef struct _stack{
char arr[101];
int topindex;
}stack;
typedef stack Stack;
void Stackinit(Stack *pstack){
pstack->topindex = -1;
}
int Empty(Stack *pstack){
if(pstack->topindex == -1){
return True;
}
else
return False;
}
char return_top(Stack *pstack){
return pstack->arr[pstack->topindex];
}
void Push(Stack *pstack,char data){
pstack->topindex = pstack->topindex + 1;
pstack->arr[pstack->topindex] = data;
}
void Pop(Stack *pstack){
pstack->topindex = pstack->topindex - 1;
}
해결방안)
첫 문자->무조건 Push를 하고 나머지 경우에 대해서 스택의 topindex값이 '(' 일때 배열의 값이 ')'이면 Pop연산을 한다
그 외에는 Push연산을 진행한다.
전체 코드
#include <stdio.h>
#include <string.h>
#define True 1
#define False 0
typedef struct _stack{
char arr[101];
int topindex;
}stack;
typedef stack Stack;
void Stackinit(Stack *pstack){
pstack->topindex = -1;
}
int Empty(Stack *pstack){
if(pstack->topindex == -1){
return True;
}
else
return False;
}
char return_top(Stack *pstack){
return pstack->arr[pstack->topindex];
}
void Push(Stack *pstack,char data){
pstack->topindex = pstack->topindex + 1;
pstack->arr[pstack->topindex] = data;
}
void Pop(Stack *pstack){
pstack->topindex = pstack->topindex - 1;
} //스택 ADT정의
int main(void){
Stack stack;
Stackinit(&stack); //스택 생성 후 초기화
int n;
scanf("%d",&n);
for(int i = 0;i<n;i++){
char array[51];
scanf("%s",array);
int size = strlen(array);
for(int j = 0;j<size;j++){ //문자열을 입력받고 문자열의 문자 검사
if(j == 0){
Push(&stack,array[j]); //처음 문자는 Push
}
else{
if(return_top(&stack) == '(' && array[j] == ')'){ //나머지 문자들에 대해서 스택 topindex가 (이고
//배열의 값이 )이면 짝이 맞으므로 Pop연산 실행
Pop(&stack);
}
else{
Push(&stack,array[j]); //그 외에는 push연산
}
}
}
if(Empty(&stack)){
printf("YES\n"); //짝이 다 맞았으면 스택이 비어있다->옳바른 문자열
}
else{
printf("NO\n"); //그렇지 않다면 옳바르지 않은 문자열
}
Stackinit(&stack); //다음 반복을 위해 스택 초기화
}
}
'자료구조' 카테고리의 다른 글
| 백준 4949번 C언어 (0) | 2021.09.17 |
|---|---|
| 큐의 개념 + 백준 10845 C언어 (0) | 2021.09.16 |
| 백준 20001번 c언어 (0) | 2021.09.15 |
| 자료구조 - 백준 10828번 스택(C언어) (0) | 2021.09.13 |
| 자료구조 - 17608번 C언어 (0) | 2021.09.12 |