스택을 사용한 괄호검사 문제

[3] 문자열 수식에서 괄호([], {}, ())의 유효성 검사 프로그램을 각각 작성.

         ① 정적 배열 스택

         ② 동적 배열 스택

 

㈜ 괄호의 우선순위는 [] > {} > () 이다.

(예) 유효: [3*(4+6)]

     비유효: (3*[4+6]), [3*(4+6)]]

---

교재에도 괄호검사가 있지만 과제와는 다르게 괄호의 우선순위까지 검사하지는 않는다. 그래서 괄호의 우선순위를 검사하기 위해 flag라는 변수를 사용했다. 일단 코드를 보면서 리뷰해보장.

먼저 정적배열스택을 사용하는 경우, 

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100
 
void push(char *stack, int *top, char input){
    (*top)++;
    stack[*top]=input;
}
 
void pop(char *stack, int *top){
    if((*top)==-1){
        printf("유효하지않음"); // ex)[]]]]]]]] stack이 비워있을 경우 
        exit(1); 
    }
    (*top)--;
}
 
int main(){
    char stack[SIZE];
    int top;
    int flag[SIZE]={4,0 },index=1, size, i;
    char input[SIZE];
    
    scanf("%s", input);
    size=strlen(input);
    
    top=-1;
    for(i=0;i<size;i++){
        if(input[i] == '['){
            if(flag[index-1]>3){
                push(stack, &top, input[i]);
                flag[index]=3;            
                index++;
            }
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='{'){
            if(flag[index-1]>2){
                push(stack,&top,input[i]);
                flag[index]=2;
                index++;
            }
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='('){
            if(flag[index-1]>1){
                push(stack,&top,input[i]);
                flag[index]=1;
                index++;
            }
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]==')'){
            pop(stack,&top);
            if(flag[--index]==1){
                continue;
            }
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='}'){
            pop(stack,&top);
            if(flag[--index]==2){
                continue;
            }
            else{
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]==']'){
            pop(stack,&top);
            if(flag[--index]==3){
                continue;
            }
            else{
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else continue;        //괄호이외의 문자 
    }
    
    printf("유효\n"); 
    
}

flag라는 다른 배열을 선언해주고 각 괄호마다 번호를 부여한후 닫는괄호가 stack에 들어올 시 일일히 확인해주는 방법으로 구현하였다. 지금 생각해보니 flag배열 또한 stack 으로 구현가능할 것 같다... 

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100
 
void push(char *stack, int *top, char input){
    (*top)++;
    stack[*top]=input;
}
 
char peek(char *stack, int top){
    if((top)==-1){
        return 'N';
    }
    else return stack[top];
}
 
char pop(char *stack, int *top){
    if((*top)==-1){
        printf("유효하지않음"); // ex)[]]]]]]]] stack이 비워있을 경우 
        exit(1); 
    }
    return stack[(*top)--];
}
 
 
int main(){
    char stack[SIZE];
    int top;
    int flag[SIZE]={4,0 },index=1, size, i;
    char input[SIZE], ch, p;
    
    scanf("%s", input);
    size=strlen(input);
    
    top=-1;
    for(i=0;i<size;i++){
        if(input[i] == '['){
            p=peek(stack, top);
            if(p=='N'){
                push(stack, &top, input[i]);
            }
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='{'){
            p=peek(stack, top);
            if(p=='N'||p=='['){
                push(stack,&top,input[i]);
            }
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='('){
            p=peek(stack, top);
            if(p=='N'||p=='['||p=='{'){
                push(stack,&top,input[i]);
            }
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]==')'){
            ch=pop(stack,&top);
            if(ch!='('){
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='}'){
            ch=pop(stack,&top);
            if(ch!='{'){
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]==']'){
            ch=pop(stack,&top);
            if(ch!='['){
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else continue;        //괄호이외의 문자 
    }
    
    printf("유효\n"); 
    
}

다시 구현했다! 생각보다 시간은 많이 안걸렸다. peek 함수를 사용하여 열린괄호의 포함관계를 구현할 수 있었다. 다 하고 보니 이렇게 간단할 수가 없는것 같아서 조금 허무하긴 하지만 그래도 언젠간 발전하겠다고 믿는다..! 동적할당하는 것도 다시 수정해야겠다. 일단 스택을 동적할당 하는 것 말고 다른부분에서 더 효율적으로 할 수 없을지 고민해봐야겠다.

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100
 
typedef struct s{
    char *stack;
    int top;
    int size;
}Stack;
 
void push(Stack *s, char input){
    s->size++;
    s->stack=(char*)realloc(s->stack, sizeof(char)*s->size);
    s->stack[++(s->top)]=input;
}
 
char peek(Stack s){
    if((s.top)==0){
        return 'N';
    }
    else return s.stack[s.top];
}
 
char pop(Stack *s){
    if((s->top)==0){
        printf("유효하지않음"); 
        exit(1); 
    }
    return s->stack[(s->top)--];
}
 
int main(){
    Stack s;
    char input[SIZE], ch, p;
    int size, i;
    
    s.top=0;            
    s.size=1;
    s.stack=(char*)malloc(sizeof(char)*s.size);
    
    scanf("%s", input);
    size=strlen(input);
    
    for(i=0;i<size;i++){
        if(input[i] == '['){
            p=peek(s);
            if(p=='N') push(&s,input[i]);
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='{'){
            p=peek(s);
            if(p=='N'||p=='[') push(&s,input[i]);
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='('){
            p=peek(s);
            if(p=='N'||p=='['||p=='{') push(&s,input[i]);
            else {                
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]==')'){
            ch=pop(&s);
            if(ch!='('){
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]=='}'){
            ch=pop(&s);
            if(ch!='{'){
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else if(input[i]==']'){
            ch=pop(&s);
            if(ch!='['){
                printf("유효하지않음\n");
                exit(1);
            }
        }
        else continue;        //괄호이외의 문자 
    }
    
    if(s.top!=0) printf("유효하지않음\n");        //stack에 괄호가 남아있음 
    else printf("유효\n"); 
    
    free(s.stack);
}

동적할당한것은 stack을 그때그때 메모리를 할당해준것말고 로직은 똑같다.