[C] Tree 로 전위, 중위, 후위 표기법 출력하기

[C] Tree 로 전위, 중위, 후위 표기법 출력하기

후위 표기법 연산을 Tree에 입력하여, 전위, 중위, 후위 표기법으로 출력 한다.

* 중위 표기법의 경우 정상적인 연산이 되도록 표시하려면 괄호를 추가하는 보완이 필요하다.

Colored By Color Scripter™

#include <stdio.h> #include <malloc.h> typedef struct _node{     int key;     struct _node *left;     struct _node *right; }node; node *head, *tail; #define MAX 100 node *stack[MAX]; int top; void init_stack(void){     top = -1; } node *push(node *t){     if (top >= MAX - 1){         printf("\n   Stack overflow");         return NULL;     }     stack[++top] = t;     return t; } node *pop(void){     if (top < 0){         printf("\n Stack underflow.");         return NULL;     }     return stack[top--]; } int is_stack_empty(void){     return (top == -1); } node *queue[MAX]; int front, rear; void init_queue(void){     front = rear = 0; } node *put(node *k){     // 큐가 꽉차면     if ((rear + 1) % MAX == front){         printf("\n    Queue overflow");         return NULL;     }     queue[rear] = k;     rear = ++rear%MAX;     return k; } node *get(void){          node *i;     if (front == rear){         printf("\n   Queue underflow");         return NULL;     }     i = queue[front];     front = ++front%MAX;     return i; } int is_queue_empty(void){     return (front == rear); } void init_tree(void){     head = (node*)malloc(sizeof(node));     tail = (node*)malloc(sizeof(node));     head->left = tail;     head->right = tail;     tail->left = tail;     tail->right = tail; } int is_operator(int k){     return (k == '+' || k == '-' || k == '*' || k == '/'); } // 후위표기법 수식에서 수식 나무 구성 node *make_parse_tree(char *p){     node *t;     while (*p){         while (*p == ' ')             p++;         t = (node*)malloc(sizeof(node));         t->key = *p;         t->left = tail;         t->right = tail;         if (is_operator(*p)){             t->right = pop();             t->left = pop();         }         push(t);         p++;     }     return pop(); } int is_legal(char *s){     int f = 0;     while (*s){         while (*s == ' ')             s++;         if (is_operator(*s))             f--;         else             f++;         if (f < 1) break;         s++;     }     return (f == 1); } void visit(node *t){     printf("%c", t->key); } // 전위 표기법 void preorder_traverse(node *t){     if (t != tail){         visit(t);         preorder_traverse(t->left);         preorder_traverse(t->right);     } } // 중위 표기법 void inorder_traverse(node *t){     if (t != tail){         inorder_traverse(t->left);         visit(t);         inorder_traverse(t->right);     } } // 후위 표기법 void postorder_traverse(node *t){     if (t != tail){         postorder_traverse(t->left);         postorder_traverse(t->right);         visit(t);     } } // 레벨 순서로 표기    (큐) void levelorder_traverse(node *t){     put(t);     while (!is_queue_empty()){         t = get();         visit(t);         if (t->left != tail)             put(t->left);         if (t->right != tail){             put(t->right);         }     } } void main(void){     char post[256] = "A B + C D - * E / F G * +";    // 후위표기법 수식 저장     // 스택, 큐, 트리 초기화     init_stack();     init_queue();     init_tree();     printf("\n\n A B + C D - * E / F G * +");     if (*post == NULL){         printf("\n Program ends...");         exit(0);     }     if (!is_legal(post)){         printf("\nExprssion is not legal");         exit(0);     }     // 수식 나무 구성     head->right = make_parse_tree(post);              printf("\nPreorder Traverse -> ");     preorder_traverse(head->right);     printf("\nInorder Traverse -> ");     inorder_traverse(head->right);     printf("\nPostorder Traverse -> ");     postorder_traverse(head->right);     printf("\nLevelorder Traverse -> ");     levelorder_traverse(head->right);     return 0; }

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