기록저장소

만들었던 Stack 함수들을 이용하여 괄호 문제를 풀어보았다. 

Stack 함수 : https://pilimage.tistory.com/12

int main(){
    int num;
    int i,j;
    int err=0;

    scanf("%d",&num);
    char input[50];

    int *errList;
    errList=(int*)malloc(sizeof(int)*num);
    Stack s;
    
    for(i=0;i<num;i++){
        memset(input,0x00,sizeof(input));
        scanf("%s",input);
        initStack(&s,strlen(input));
        for(j=0;j<strlen(input);j++){
            if(input[j]=='('){
                pushStack(&s,input[j]);
            }else{
                if(popStack(&s)==0){
                    errList[i]=1;
                }
            }
        }
        if (!isEmptyStack(&s)){
            errList[i]=1;
        }
        DelStack(&s);
    }

    for(i=0;i<num;i++){
        if(errList[i]){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    free(errList);
    return 0;
}

입력을 받아서 ' ( '를 만나면 스택에 push하고 ' ) '를 만나면 pop을 하도록하였다. 

' ) '을 만나서 pop을 할때, ' ( '와 ' ) '는 한 쌍이므로 ' ) '를 만났는데 스택에 ' ( '가 없어서 pop을 하지 못한다면 에러로 처리하였다. 

입력을 다 서치하고, 스택에 데이터인 ' ( '가 남아 있다면 에러로 처리하였다.

err flag과 errList를 이용하여 마지막에 결과를 출력하도록 하였다.

끝

Stack이란?

: 데이터를 일시적으로 저장하는 방법

LIFO (Last In First Out, 후입선출)의 구조로나중에 들어온 데이터가 먼저 나가는 방식

배열을 크게 잡고 사용하여도 되지만 학습을 위하여 malloc을 사용하였다. 

typedef struct 
{
    int size;
    int idx;
    int *data;
}Stack;

void DelStack(Stack *s){
    free(s->data);
}


int initStack(Stack *s, int size){
    s->size=size;
    s->idx=-1;
    s->data=(int*)malloc(sizeof(int)*(s->size));
    if(s->data!=NULL){
        return 1; 
    }else{
        s->size=0;
        return 0; 
    }   
}

구조체 Stack의 멤버 변수로는 스택의 크기 : size , 데이터 index : idx , 데이터 : *data 

initStack을 통해 스택 구조체를 초기화한다. 

idx는 -1로 초기화하고 malloc이 실패했을때 initStack이 0을 리턴하도록 한다. 

int isFullStack(Stack *s){
    if(s->idx>=s->size-1){
        return 1;
    }else{
        return 0;
    }
}
int isEmptyStack(Stack *s){
    if(s->idx==-1){
        return 1;
    }else{
        return 0;
    }
}

int pushStack(Stack *s, int data){
    if(isFullStack(s)){
        // printf("Stack is Full\r\n");
        return 0;
    }else{
        s->idx++;
        s->data[s->idx]=data;
        return 1;
    }
    return 0;
}
int popStack(Stack *s){
    int val=0;
    if(isEmptyStack(s)){
        // printf("stack is Empty");
        return val;
    }else{
        val=s->data[s->idx];
        s->idx--;
        return val;
    }    
}

isFullStack : 스택이 가득 찼는지 확인

isEmptyStack: 스택이 비었는지 확인 

pushStack : 스택에 데이터 삽입

-> 스택이 가득 차지 않았을 경우, 데이터 인덱스를 옮기고 데이터를 넣는다.

idx를 -1로 초기화 하였기 때문에 idx를 먼저 더해서 옮기고 데이터를 넣었다. 만약 idx를 0으로 초기화하였다면 데이터를 넣고 idx를 더해주면 된다. 

popStack : 스택에서 데이터 출력

->스택이 비어있지 않을 경우, 데이터를 출력하고 인덱스를 옮긴다. 

int SearchStack(Stack *s, int data){
    int i;
    for(i=0;i<s->idx;i++){
        if(data==s->data[i]){
            return i;
        }
    }
    return -1;
}

조금의 응용으로  SearchStack은 스택에 찾으려는 데이터가 있으면 해당 인덱스를 없으면 -1을 리턴하도록 만들어보았다. 

만든 함수를 아래와 같이 테스트하였다.

int main(){
    int i;
    Stack stack;
    initStack(&stack,10);
    pushStack(&stack,1);
    pushStack(&stack,2);
    pushStack(&stack,3);
    pushStack(&stack,4);
    pushStack(&stack,5);
    pushStack(&stack,6);
    pushStack(&stack,7);
    pushStack(&stack,8);
    pushStack(&stack,9);
    pushStack(&stack,10);

    pushStack(&stack,11);
    printf("search %d %d\r\n",SearchStack(&stack,7),SearchStack(&stack,-1));    

    for(i=0;i<13;i++){
        printf("% d idx:%d\r\n",popStack(&stack),stack.idx);

    }
    DelStack(&stack);
    return 0;

}

1. 크기가 10인 사이즈를 만들고 11개의 데이터를 넣었다. - > Stack is Full 출력

2. 데이터가 7인 인덱스와 -1인 인덱스를 서치하였다 -> serach 6 -1 출력

3. 13개의 데이터를 출력하였다 -> 10 idx : 9~~ stack is Empty 0 idx : -1 출력 

끝