Infix를 Postfix로 바꾸기. (스택 푸시팝 연습)

스택 푸시팝은 아마 제가 코딩하면서 가장 많이 쓰는 알고리즘 중 하나일겁니다.

간단하게 기억을 되돌릴 일이 있을 때 (?) 자주 쓰는 예제입니다.

항상 연습하자, 연습.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_STACK_SIZE 100 typedef char element; typedef struct{ element stack[MAX_STACK_SIZE]; int top; }stacktype; void init(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)){ printf("스탯 포화\n"); return; } else s->stack[++(s->top)] = item; } element pop(stacktype *s){ if(is_empty(s)){ printf("스택 공백"); exit(1); } else return s->stack[(s->top)--]; } element peek(stacktype *s){ if(is_empty(s)){ printf("스택 공백"); exit(1); } else return s->stack[s->top]; } int prec(char op){ switch(op){ case '(' : case ')' : return 0; case '&' : case '^' : return 1; case '+' : case '-' : return 2; case '*' : case '/' : case '%' : return 3; } return -1; } void infix_to_postfix(char exp[], char res[]){ int i=0, j=0; char ch, top_op, cx; int len = strlen(exp); stacktype s; init(&s); for(i=0; i<len; i++){ ch = exp[i]; switch(ch){ case'+' : case '-' : case '*' : case '/' : case '&' : case '^' : case '%' : while(!is_empty(&s) && (prec(ch) <= prec(peek(&s)))){ printf("%c", cx=pop(&s)); res[j++] = cx; } push(&s, ch); break; case '(' : push(&s, ch); break; case ')' : top_op = pop(&s); while(top_op != '('){ printf("%c", top_op); res[j++] = top_op; top_op = pop(&s); } break; default : printf("%c", ch); res[j++] = ch; break; } } while (!is_empty(&s)){ printf("%c", cx = pop(&s)); res[j++] = cx; } } int main(){ int len; int index; int copy_len; int end_flag = 0; char res[100] = {0,}; char exp[100]; FILE *fp; fp = fopen("in.txt", "r"); if(fp != NULL){ fgets(exp, 100, fp); //puts(strcat(exp, "읽음")); fclose(fp); } else{ printf("파일 에러"); } while (end_flag==0){ len = strlen(exp); for(index = 0; index < len-1; index++){ if(exp[index] == ' '){ copy_len = len - index; memcpy(exp + index, exp+index+1, copy_len); break; } } if(index == len-1) end_flag = 1; } printf("읽은 문자열 = %s\n\n", exp); infix_to_postfix(exp, res); printf("\n\n"); return 0; }