Stack -(Quize3)

🎈1. 문제

🎆2. 소스코드 + 주석

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

int err = 0;

typedef char element;

typedef struct {
        element data[MAX_STACK_SIZE];
        int top;
} StackType;

//초기화 함수
void init_stack(StackType *s)
{
        s->top = -1;
}
//공백 상태 검출 함수
int is_empty(StackType *s)
{
        return (s->top == -1);
}

//포화 상태 검출 함수
int is_full(StackType *s)
{
        return (s->top == (MAX_STACK_SIZE - 1));
}

//삽입 함수
void push(StackType *s, element item)
{
        if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
        else s->data[++(s->top)] = item;
}
//삭제 함수

element pop(StackType *s)
{ if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
        }
else return s->data[(s->top)--];

}
 //피크 함수
element peek(StackType *s)
{
        if (is_empty(s)) {
                fprintf(stderr, "스택 공백 에러\n");
                exit(1);
        }
        else return s->data[s->top];
}

//후위 표기 수식 계산 함수
int eval(char exp[])
{
        int op1, op2, value, i = 0;
        int len = strlen(exp);
        char ch;
        StackType s;


        init_stack(&s); //스택초기화 ( 생성)
        for (i = 0; i < len; i++) {
        ch = exp[i];
        if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
                value = ch - '0';//입력이 피연산자이면
                push(&s, value);
        }
        else { //연산자이면 피연산자를 스택에서 제거
        op2 = pop(&s);
        op1 = pop(&s);
        switch (ch) { //연산을 수행하고 스택에 저장
        case '+': push(&s, op1 + op2); break;
        case '-': push(&s, op1 - op2); break;
        case '*': push(&s, op1 * op2); break;
        case '/': push(&s, op1 / op2); break;
                }
        }
}
        return pop(&s);
}
 //연산자의 우선 순위를 반환한다.
int prec(char op)
{ switch (op) {
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
        }
return -1;
}

void check_error(element exp[]) {
        err = -1;
        int len = strlen(exp);

        //오류 0 : 연산자후 0이 오면 예외처리
        for (int i = 0; i < len; i++) {
                if (i + 1 < len && exp[i] == '/' && exp[i + 1] == '0') {
                        printf("계산결과 : ");
        printf("오류 : 0으로 나눌 수 없습니다.\n\n");
        err = 0;
        break;
        }
}

        int count = 0;
//오류 1 : 괄호의 짝이 맞지 않으면 예외처리
for (int i = 0; i < len; i++) {
        if (exp[i] == '(') {
        count++;
        }
        else if (exp[i] == ')') {
                count--;
                }
        }
        if (count > 0) {
        printf("계산 결과\n");
        printf("오류1: 괄호 매칭 불가능\n\n");
        err = 1;
        }
        else if (count < 0) {
        printf("계산 결과\n");
        printf("오류1: 괄호 매칭 불가능2\n\n");
        err = 1;
        }

//오류 2 : 예외 문자 포함
        for (int i = 0; i < len; i++) {
        if (exp[i] == '(' || exp[i] == ')') {
                continue;
        }
        else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {
                continue;
        }
        else if ('0' <= exp[i] && exp[i] <= '9') {
                continue;
        }
        else {
                printf("계산결과\n");
                printf("오류2: 예외 문자 포함\n\n");
                err = 2;
        }
}

//한자리 수 이상의 수 입력에 대해 예외처리

int count_len = 0;
int max_len = 0;
for (int i = 0; i < len; i++){
        if ('0' <= exp[i] && exp[i] <= '9') {
                count_len++;
                if (count_len >= max_len) {
                        max_len = count_len;
                }
        }
        else { count_len = 0;
        }
        }
if (max_len >= 2) {
        printf("계산결과\n");
        printf("오류 3: 한 자리수 이상의 입력 포함\n\n");
        err = 3;
        }
}
//수식 변환 함수

element* infix_to_postfix(element exp[]) {

                //입력받은 표기식 오류 검사
        check_error(exp);
        //오류가 있다면 다시 실행
        if (err != -1) {
                return NULL;
        }
        int i, idx = 0; //i는 for문 제어 변수 ,idx 는 post_arr의 inded
        int len = strlen(exp);
        char ch, op;
        StackType s;
        element* postfix_arr = (element*)malloc(MAX_STACK_SIZE);
        if (postfix_arr == NULL) {
                fprintf(stderr, "메모리 할당 에러\n");
                exit(1);
        }

        init_stack(&s); //스택 촉기화

        // 중위 표기식으로 표현된 식을 순회
        for (int i = 0; i < len; i++) {

                        // 값을 뽑는다
                ch = exp[i];
                //일반 숫자라면 그래도 postfix_arr에 추가
                if ('0' <= ch && ch <= '9') {
                        postfix_arr[idx++] = ch;
                }

//연산자 +,-,/라면
                else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {

                        while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
                        {
                                        //해당 값들은 모두 추가해 준다.
                                postfix_arr[idx++] = peek(&s);
                                pop(&s);
                        }
                        //자기 자신을 스택에 추가한다.
                        push(&s, ch);
                }
//'('는 무조건 스택에 추가한다.
                else if (ch == '(') {
                        push(&s, ch);
                }
//')'가 나오면 '('가 나올때까지 스택에서 pop하여 추가해준다.
                else if (ch == ')') {
                        op = pop(&s);
                        while (op != '(')
                        {
                                postfix_arr[idx++] = op;
                                op = pop(&s);
                        }
                }
        }

        //아직 스택에 남아있는 값들을 모두 추가해준다.
        while (!is_empty(&s))
        {
                op = peek(&s);
                pop(&s);
                postfix_arr[idx++] = op;
        }
// 문자열의 끝을 지정해준다.
        postfix_arr[idx] = '\0';
        return postfix_arr;
}


int main(void) {
        element expression[MAX_STACK_SIZE];
        char word[100];
        //중위 표시식 입력
                printf("실행 결과\n");
                printf("수식을 입력하세요 : ");
                scanf("%s", expression);
                //중위 표기식 및 결과 값 표시
                element *result = infix_to_postfix(expression);
                if (err == -1) {
                        printf("후위식 : %s\n", result);
                        printf("계산결과 : %d\n\n", eval(result));
                }


        return 0;
}

🎇3. 실행 결과

✨4. 느낌점&설명

이번 퀴즈에서는 스택을 이용한 중위표기법을 후위 표기법으로 변환하는 계산법이랑 그 결과 값을 출력하는 프로그램을 만드는 활동을 하였다. 먼저 이번 프로그램을 구현하기 위해서는 기본적인 스택의 동적할당과 스택 함수에 대한 완벽한 숙지가 필요했으며, 이 문제의 특징으로, 중위 표기법을 후위 표기법으로 변환하는 벙법과 후위 표기법 계산방법과 이를 구현하기 위한 절차를 생각하는 것이 가장 중요했다. 먼저 중위 표기법을 후위 표기법으로 변환하는 절차는 간단하게 피연사자가 들어오면 바로 출력하고 연산자가 들어오면 자기보다 우선순위가 높거나 같은것들을 빼고 자신을 스택에 담은 뒤 ‘(’를 만나면 무조건 스택에 담고, 닫는 괄호 ‘)를 만나면 “(”를 만날 때 까지 스택에서 출력하는 것으로 이러한 절차를 통해 스택에 있는 연산자 우선순위를 이용하면 중위 표기법을 후위 표기법으로 변환 할 수 있겠다고 생각하였다. 그리고 후위 표기법 계산은 피연산자를 만나면 스택에 담고 연산자를 만나면 스택에서 두 개의 연산자를 꺼내서 연산한 뒤 그 결과를 스택에 담아 연산을 마치고 스택에 남아있는 하나의 피연산자가 연산 수행의 결과가 되면 후위 표기법 계산을 완료하는 절차를 통해 코드를 구성 할 수있게 되었다. 이렇게 후위 표기법 계산이랑 중위 표기법을 후위 표기법으로 변환하는 코드를 퀴즈를 풀때는 시간내 스스로 풀지는 못 하였지만, 퀴즈가 끝난 후 후위 표기법과 변환하는 절차를 천천히 살펴보고 이해하면서 많은 시간을 투자하여 프로그램을 구현 할 수 있었다. 이번 퀴즈를 통해 스스로 스택을 완벽하게 구현하기 위해 스택을 이용한 다양한 예제 문제를 코딩사이트에서서 찾아보고 스택에 대한 이해를 더 높여 스택을 스스로 완벽하게 구현해야겠다고 생각하는 계기가 되었고,앞으로 퀴즈를 풀고 퀴즈와 연관된 문제를 많이 풀어봐야겠다는 생각도 들었다.