회문(Palindrome) 검사 (스택)

회 문 ( p a l i n d r o m e ) 이 란 앞 뒤 어 느 쪽 에 서 읽 어 도 같 은 단 어 를 의 미 한 다 . 예 를 들 면 " e y e n
" m a d a m , I ' m A d a m " , " r a c e c a r " 등 이 다 . 여 기 서 물 론 구 두 점 이 나 스 페 이 스 , 대 소 문 자 등 은 무
시 하 여 야 한 다 . 스 택 을 이 용 하 여 주 어 진 문 자 열 이 회 문 인 지 아 닌 지 를 결 정 하 는 프 로 그 램 을 작 성
하 라 

---

기본적인 스택의 기능은 구현해둔 코드를 사용하였다.

2024.07.22 - [Algorithm] - 스택 (stack)

스택 (stack)

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    int top;
    char data[1000];
}Stack;

void initStack(Stack *s) {
    s->top = -1;
}
int isEmptyStack(Stack *s) {
    return s->top == -1;
}
int isFullStack(Stack *s) {
    return s->top == 1000;
}
void push(Stack *s, char data) {
    if(isFullStack(s)) {
        fprintf(stderr, "Stack is full\n");
        exit(1);
    }
    s->data[++s->top] = data;
}
char pop(Stack *s) {
    if(isEmptyStack(s)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    return s->data[s->top--];
}
void printStack(Stack *s) {
    if(isEmptyStack(s)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    for(int i = s->top; i >= 0; i--) {
        printf("%c ", s->data[i]);
    }

    printf("\n");
}

---

회문 검사를 위해 스택을 사용한 방법으로는 문장을 입력받아 각 문자를 스택에 하나씩 저장하고,

저장된 순서를 뒤집어 새로운 스택에 저장하고, 이 두 스택을 각 인덱스별로 비교하여 같은 스택인지를 확인한다.

입력을 받을때 주의할 점은, 알파벳 소문자와 대문자를 하나로 통일하여 스택에 push할 수 있도록 하며

따옴표나 띄어쓰기 쉼표 등의 특수문자와 기호들은 스택에 push하지 않는다는 것이다.

이를 처리하기 위해 아래와 같은 입력 방식을 사용하였다.

int main(void) {
    printf("문자열을 입력히시오. : ");
    char input[1000];
    fgets(input,sizeof(input),stdin);

    Stack s;
    initStack(&s);
    for (int i = 0; i < strlen(input); i++) {
        if(input[i] >= 'a' && input[i] <= 'z') {
            char tmp = input[i] - 32;
            push(&s,tmp);
        }
        else if(input[i]>='A' && input[i]<='Z') {
            char tmp= input[i];
            push(&s,tmp);
        }
        else if(input[i]==' '||input[i]==','||input[i]=='\''||input[i]=='.'||input[i]=='"') {
            continue;
        }
    }
    //이후 스택 출력 코드
    return 0;
}

---

다음으로 스택을 뒤집는 함수와 이후 같은 스택인지 검사하는 함수를 만들었다.

//스택 뒤집어 push한 스택2
    Stack reverseS=reverse(&s);
    printStack(&reverseS);

    printf("first stack size: %d\n",getStackSize(&s));
    printf("second stack size: %d\n",getStackSize(&reverseS));

    if(isSameStack(&s,&reverseS)) {
        printf("Palindrome\n");
    }
    else {
        printf("Not a palindrome\n");
    }

메인함수에서는 위와 같이 사용하였고,

함수를 뒤집는 reverse()함수는 아래와 같다.

Stack reverse(Stack *s) {
    Stack tempStack;
    initStack(&tempStack);
    for(int i=s->top;i>=0;i--) {
        push(&tempStack, s->data[i]);
    }
    return tempStack;  // Return the reversed stack
}

스택이 같으면 1을 반환하고, 다르면 0을 반환하도록 하는 isSameStack()함수는 아래와 같다.

int isSameStack(Stack *a, Stack *b) {
    if(a->top != b->top) {
        return 0;
    }
    for(int i=0;i<=a->top;i++) {
        if(a->data[i]!=b->data[i]) {
            return 0;
        }
    }
    return 1;
}

---

출력은 다음과 같다.

 

 

---

전체 코드:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    int top;
    char data[1000];
}Stack;

void initStack(Stack *s) {
    s->top = -1;
}
int isEmptyStack(Stack *s) {
    return s->top == -1;
}
int isFullStack(Stack *s) {
    return s->top == 1000;
}
void push(Stack *s, char data) {
    if(isFullStack(s)) {
        fprintf(stderr, "Stack is full\n");
        exit(1);
    }
    s->data[++s->top] = data;
}
char pop(Stack *s) {
    if(isEmptyStack(s)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    return s->data[s->top--];
}
void printStack(Stack *s) {
    if(isEmptyStack(s)) {
        fprintf(stderr, "Stack is empty\n");
        exit(1);
    }
    for(int i = s->top; i >= 0; i--) {
        printf("%c ", s->data[i]);
    }

    printf("\n");
}

Stack reverse(Stack *s) {
    Stack tempStack;
    initStack(&tempStack);
    for(int i=s->top;i>=0;i--) {
        push(&tempStack, s->data[i]);
    }
    return tempStack;  // Return the reversed stack
}

int isSameStack(Stack *a, Stack *b) {
    if(a->top != b->top) {
        return 0;
    }
    for(int i=0;i<=a->top;i++) {
        if(a->data[i]!=b->data[i]) {
            return 0;
        }
    }
    return 1;
}
int getStackSize(Stack *s) {
    return s->top+1;
}

int main(void) {
    printf("문자열을 입력히시오. : ");
    char input[1000];
    fgets(input,sizeof(input),stdin);

    Stack s;
    initStack(&s);
    for (int i = 0; i < strlen(input); i++) {
        if(input[i] >= 'a' && input[i] <= 'z') {
            char tmp = input[i] - 32;
            push(&s,tmp);
        }
        else if(input[i]>='A' && input[i]<='Z') {
            char tmp= input[i];
            push(&s,tmp);
        }
        else if(input[i]==' '||input[i]==','||input[i]=='\''||input[i]=='.'||input[i]=='"') {
            continue;
        }
    }
    printStack(&s);

    //스택 뒤집어 push한 스택2
    Stack reverseS=reverse(&s);
    printStack(&reverseS);

    printf("first stack size: %d\n",getStackSize(&s));
    printf("second stack size: %d\n",getStackSize(&reverseS));

    if(isSameStack(&s,&reverseS)) {
        printf("Palindrome\n");
    }
    else {
        printf("Not a palindrome\n");
    }

    return 0;
}