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

Posted at 2015.02.19 11:33 | Posted in C



facebook에 글올리기



[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;
}



이웃추가
facebook에 글올리기
,

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기