[자료구조] 스택 스택의 응용 예제 후위표기 수식의 계산 (2024)

신고하기

#include <stdio.h>#include <stdlib.h>#define MAX_STACK_SIZE 100typedef 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'; // char형으로 입력된 데이터를 int형으로 변환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 main(){int result;printf("후위표기식은 82/3-32*+\n");result = eval("82/3-32*+");printf("결과값은 %d\n", result);return 0;}

#include <stdio.h>#include <stdlib.h>#define MAX_STACK_SIZE 100typedef 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 prec(char op){switch (op){case '(': case ')': return 0;case '+': case '-': return 1;case '*': case '/': return 2;}return -1;}// 중위표기 수식 -> 후위표기 수식 변환void infix_to_postfix(char exp[]){int i = 0;char ch, top_op;int len = strlen(exp);StackType s;init_stack(&s);for (i = 0; i < len; i++){ch = exp[i];switch (ch){case '+': case '-': case '*': case '/': // 연산자// 스택에 있는 연산자의 우선순위가 더 크거나 같으면 출력while (!is_empty(&s) && prec(ch) <= prec(peek(&s))){printf("%c", pop(&s));}push(&s, ch);break;case '(': // 왼쪽 괄호push(&s, ch);break;case ')': // 오른쪽 괄호top_op = pop(&s);// 왼쪽 괄호를 만날 때까지 출력while (top_op != '('){printf("%c", top_op);top_op = pop(&s);}break;default: // 피연산자printf("%c", ch);break;}}while (!is_empty(&s)) // 스택에 저장된 연산자들 출력{printf("%c", pop(&s));}}int main(){char* s = "(2+3)*4+9";printf("중위표기 수식 %s \n", s);printf("후위표기 수식 ");infix_to_postfix(s);printf("\n");return 0;}