[C] 후위표기법 1 Stack_LinkedList[C] 후위표기법 1 Stack_LinkedList

Posted at 2015.02.15 10:34 | Posted in C



facebook에 글올리기



[C] 후위표기법 1 Stack_LinkedList


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


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

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

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

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


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



 Colored By Color Scripter

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



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


Colored By Color Scripter

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



저작자 표시 비영리 변경 금지
신고

'C' 카테고리의 다른 글

[C] Queue 배열로 구현  (0) 2015.02.15
[C] 사칙연산 계산 (후위표기법)  (1) 2015.02.15
[C] 후위표기법 1 Stack_LinkedList  (1) 2015.02.15
[C] 스택(Stack) LinkedList  (0) 2015.02.14
[C] 스택(Stack) 배열형  (0) 2015.02.14
[C] 이중 연결 리스트 (Doubly Linked List)  (0) 2015.02.14
이웃추가
facebook에 글올리기
  1. 이건 연산은 안하고 저장만 하는건가요..??

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기