[C] 후위표기법 1 Stack_LinkedList

[C] 후위표기법 1 Stack_LinkedList

링크드 리스트의 스택을 활용하여 중위표기법을 후위표기법으로 변경해보자

1. '(' 문자는 무시하고 넘어간다

2. 피연산자는 그대로 출력한다.

3. 연산자는 스택에 푸시한다.

4. ')'를 만나면 스택에서 팝하여 출력한다.

아래 알고리즘의 단점은 연산자 우선 순위가 고려되지 않아 중위표기법에 괄호를 씌워야 한다.

void postfix1(char *dst, char *src){     char c;     init_stack();     while (*src){         if (*src == ')'){             *dst++ = pop();             *dst++ = ' ';             src++;         } else if(*src=='+' || *src=='-' || *src=='*' || *src=='/'){             push(*src);             src++;         }         else if (*src >= '0' && *src <= '9'){             do{                 *dst++ = *src++;             } while (*src >= '0' && *src <= '9');                          *dst++ = ' ';         }         else{             src++;         }              }     while (head->next != tail){         *dst++ = pop();         *dst++ = ' ';     }     *dst = 0; }

아래는 스택과 메인을 포함한 전체 소스코드이다.

#include <stdio.h> #include <malloc.h> typedef struct _node{     int key;     struct _node *next; } node; node *head, *tail; void init_stack(void){     head = (node*)malloc(sizeof(node));     tail = (node*)malloc(sizeof(node));     head->next = tail;     tail->next = tail; } int push(int k){     node *t;     if ((t = (node*)malloc(sizeof(node))) == NULL){         printf("\n   Out of memory....");         return -1;     }     t->key = k;     t->next = head->next;     head->next = t;     return k; } int pop(void){     node *t;     int i;     if (head->next == tail){         printf("\n   Stack underflow");         return -1;     }     t = head->next;     i = t->key;     head->next = t->next;     free(t);     return i; } void clear_stack(void){     node *t, *s;     t = head->next;     while (t != tail){         s = t;         t = t->next;         free(s);     }     head->next = tail; } void print_stack(void){          node *t;     t = head->next;     printf("\n Stack contents : TOP ------> Bottom \n");     while (t != tail){         printf("%-6d", t->key);         t = t->next;     } } void postfix1(char *dst, char *src){     char c;     init_stack();     while (*src){         if (*src == ')'){             *dst++ = pop();             *dst++ = ' ';             src++;         } else if(*src=='+' || *src=='-' || *src=='*' || *src=='/'){             push(*src);             src++;         }         else if (*src >= '0' && *src <= '9'){             do{                 *dst++ = *src++;             } while (*src >= '0' && *src <= '9');                          *dst++ = ' ';         }         else{             src++;         }              }     while (head->next != tail){         *dst++ = pop();         *dst++ = ' ';     }     *dst = 0; } int main(void){     char infix[20] = "(3*7)+(8/4)-3";     char postfix[20];          postfix1(postfix, infix);     printf("%s", postfix);          return 0; }

출처: https://hyeonstorage.tistory.com/347?category=622873 [개발이 하고 싶어요]