[자료구조] 중위표기식 -> 후위표기식 -> 후위표기식연산

=중위 표기식 -> 후위 표기식 -> 연산 =
채진석교수님 강의 - 자료구조 2학년 1학기 코딩과제

#include <stdio.h>
#include <string.h>

#define MAX_STATCK_SIZE 100             // 스택의 최대 크기 
#define MAX_EXP_SIZE 100                // 수식의 최대 크기 

typedef enum { lparen, rparen, plus, minus, multiply, divide, eos, operand } precedence;

int stack_eval[MAX_STATCK_SIZE];
precedence stack_postfix[MAX_STATCK_SIZE];
char exp[MAX_EXP_SIZE];

// lparen, rparen, plus, minus, multiply, divide, eos의 우선순위 값
static int PIS[] = { 0, 3, 1, 1, 2, 2, 0 };
static int PIE[] = { 4, 3, 1, 1, 2, 2, 0 };

void push_eval(int*, int);
int pop_eval(int*);
void push_postfix(int*, precedence);
precedence pop_postfix(int*);
int evalPostfix(void);
precedence getToken(char*, int*);
void postfix(void);
char makeToken(precedence);

int evalPostfix(void)
{
	precedence token;
	char symbol;
	int op1, op2; //피연산자 두개를 받는다.
	int n = 0;
	int top = -1;
	token = getToken(&symbol, &n);
	// printf("token = %d, symbol= %c\n",token, symbol);
	while(token != eos){
		if(token == operand) push_eval(&top, symbol-'0');
		else{
			op2 = pop_eval(&top);
			op1 = pop_eval(&top);
			switch(token) {
				case plus : push_eval(&top, op1 + op2); break;
				case minus : push_eval(&top, op1 - op2); break;
				case multiply : push_eval(&top, op1 * op2); break;
				case divide : push_eval(&top, op1 / op2); break;
			}
		}
		token = getToken(&symbol, &n);
	}
	return pop_eval(&top);
}

void postfix(void)
{
	char symbol; 
	int i=0; // exp배열 인덱스
	int j, k;
	int n=0; 
	int top = -1; 
	int array[MAX_EXP_SIZE];
	precedence token; 
	token = getToken(&symbol, &n);
	while( token != eos ){ 
		switch ( token ) {
		case operand :
			exp[i++] = symbol; 
			break;
		case rparen :
			while( stack_postfix[top] != lparen ) exp[i++] = makeToken(pop_postfix(&top));
			token = pop_postfix(&top);	// 필요없어진 lparen을 버리기 위해 사용
			break;
		default :
			while( PIE[token] <= PIS[stack_postfix[top]] ) exp[i++] = makeToken(pop_postfix(&top));
			push_postfix(&top, token);          
			break;
		}
		token = getToken(&symbol, &n); 
	}
	while( top > -1 ) exp[i++] = makeToken(pop_postfix(&top)); 
	exp[i]=NULL; 
}

void push_eval(int *top, int item)
{
        if (*top >= MAX_STATCK_SIZE-1) {
                printf("Stack is full.\n");
                return;
        }
        stack_eval[++*top] = item;
}

int pop_eval(int *top)
{
        if (*top < 0) {
                printf("Stack is empty.\n");
                return -1;
        }
        return stack_eval[(*top)--];
}

void push_postfix(int *top, precedence item)
{
        if (*top >= MAX_STATCK_SIZE-1) {
                printf("Stack is full.\n");
                return;
        }
        stack_postfix[++*top] = item;
}

precedence pop_postfix(int *top)
{
        if (*top < 0) {
                printf("Stack is empty.\n");
                return eos;
        }
        return stack_postfix[(*top)--];
}

precedence getToken(char *symbol, int *n)
{
        *symbol = exp[(*n)++];
        switch (*symbol) {
                case '(' : return lparen;
                case ')' : return rparen;
                case '+' : return plus;
                case '-' : return minus;
                case '*' : return multiply;
                case '/' : return divide;
                case '\0' : return eos;
                default : return operand;
        }
}

char makeToken(precedence token)
{
        switch (token) {
                case plus : return '+';
                case minus : return '-';
                case multiply : return '*';
                case divide : return '/';
                default : return ' ';
        }
}

int main()
{		        
        int result;
        printf("중위 표기식 입력 (종료시는 xxx) : ");
        scanf("%s", exp);
        while (strcmp(exp, "xxx")) {
                postfix();
                printf("\n변환된 후위 표기식 : %s\n", exp);
                result = evalPostfix();
                printf("\n계산 결과 : %d\n", result);
                printf("\n중위 표기식 입력 (종료시는 xxx) : ");
                scanf("%s", exp);
        }
        return 0;
}