중위표현을 후위표현으로

스택을 이용하여 중위표현(infix notation)을 후위표현(postfix notation)

으로 바꾸는 프로그램이다.

스택의 구현과, 연산자의 우선순위, 토큰을 잘라내는 것,

괄호 '(', ')' 의 특별취급등을 포함하고 있는 프로그램으로

자료구조 프로그램 중에서 비교적 자주 다루어 지는 프로그램이다.

보통 초보자들이 작성하는 프로그램에서는 난이도를 고려하여

피연산자는 한자리 정수로 한정한다. 

이 프로그램도 피연산자를 한자리 정수로 한정하고 식에 스페이스를

넣지 않는다고 가정하고 풀었다.

스택의 구현은 정수의 배열로 하였으며 top을 나타내기 위하여 

0번째 원소를 스택의 top을 나타내는 방식으로 구현하였다.

이렇게 스택을 구현하면, 정수의 스택에만 한정되기는 하지만,

구현이 아주 깔끔해 지게 된다. 인자를 넘길 때도 그냥 정수의 배열의

주소만 넘기면 되기 때문에 편리하다.

#include <stdio.h>

#include <stdlib.h>

// 연산자 우선순위을 구하는 함수

// 곱셈과 나눗셈의 우선순위가 덧셈이나 뺄셈보다 더 높다.

int precedence(int op) {

    if(op=='(') return 0;

    if(op=='+'||op=='-') return 1;

    if(op=='*'||op=='/') return 2;

    return 3;

}

// 괄호, 피연산자(숫자), 숫자만 나오므로

// 숫자인지를 구하는 함수를 사용하면 된다.

int isnumber(int k) {

    return '0'<=k && k<='9';

}

// 스택을 초기화 하는 것은 아주 간단하다.

// 스택의 top을 나타내는 0번째 원소에 0을 넣어 주기만 하면 된다.

void initstack(int s[]) {

    s[0]=0;

}

// push는 스택의 주소와 값을 인자로 가진다.

// 스택의 크기를 50으로 잡았으므로 49가 되면 full이 된다.

// top을 위한 공간을 한개 필요로 하므로, 실제로 스택을 위한 공간은

// 1이 줄어 들게 된다.

// 처음 스택에 push를 하는 경우를 생각해 보면 스택의 1번째 방에

// 값이 들어가야 한다는 것을 알수 있다.

// 따라서 먼저 스택의 0번째 원소를 증가시키고

// 스택의 top이 가리키는 장소에 값을 넣으면 된다.

void push(int s[], int v) {

    if(s[0]<49) s[++s[0]]=v;

    else {

        printf("스택이 꽉 찼습니다.");

        exit(1);

    }

}

// pop은 스택의 주소만 인자로 가진다.

// 스택의 top이 가리키는 방의 값이 반환된다.

// 그리고 스택의 top이 1이 줄게 된다.

// 스택의 top은 스택에 들어있는 원소의 갯수와도 같다.

int pop(int s[]) {

    if(s[0]>0) return s[s[0]--];

    printf("스택이 비었습니다.");

    exit(1);

}

// top 은 스택의 top이 가리키는 값을 반환한다.

int top(int s[]) {

    if(s[0]>0) return s[s[0]];

    printf("스택이 비었습니다.");

    exit(1);

}

// 스택이 empty인지는 top이 0인지를 검사하면 된다.

int isempty(int s[]) {

    return s[0]==0;

}

int main() {

    char infix[100];

    // 스택의 top 을 가리키는 변수는 stack[0] 입니다.

    int stack[50]={0,};;

    int i, x, y;

    printf("중위 표기법: ");

    scanf("%s",infix);

    printf("후위 표기법: ");

    i=0;

    while((x=infix[i])>0) {

        // 왼괄호는 push한다.

        if(x=='(') push(stack,x);

        // 오른괄호를 만나면 왼괄호까지를 모두 pop하면서 출력한다.

        else if(x==')') {

            while((y=pop(stack))!='(') printf("%c ",y);

        }

        // 숫자이면 출력한다.

        else if(isnumber(x)) printf("%c ",x);

        // 연산자이다. 

        // 스택의 연산자의 우선순위가 

        // 현재 연산자의 우선순위보다 같거나 높은 경우에는 

        // 모두 pop하여 출력한다.

        // 그다음 push한다.

        else { 

            while(!isempty(stack)&&precedence(top(stack))>=precedence(x))

                printf("%c ", pop(stack));

            push(stack, x);

        }

        i=i+1;

    }

    // 스택에 남아있는 연산자를 모두 pop하며 출력한다.

    while(!isempty(stack)) printf("%c ", pop(stack));

    return 0;

}