[자료구조] 중위식을 후위식으로 변환하기

[자료구조] 중위식을 후위식으로 변환하기

728x90

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100

char expr[MAX_EXPR_SIZE];
int top = -1;

int stack[MAX_STACK_SIZE];
/* isp and icp arrays ? index is value of precedence lparen, rparen,
	plus, minus, times, divide, mode, eos */
    
void push(int item){

	if (top > = MAX_STACK_SIZE -1){
    	printf("stack_full()\n");
        return;
    }
    stack[++top] = item; // 스택의 ++top 번째 요소에 item 집어넣기.
}

int pop(){
	if (top == -1){
    	printf("stack_empty()\n");
    }
    return stack[top--]; // 현재 상태의 스택값 반환하고 top--하기.
}

int isempty(){
	if(top == -1)
    	return 1;
    else
    	return 0;
}

int isfull(){
	if(top >= MAX_STACK_SIZE -1)
    	return 1;
    else
    	return 0;
}

static int isp[] = {0,19,12,12,13,13,13,0};
static int icp[] = {20,19,12,12,13,13,13,0};

int get_token(char* symbol, int* n){
	*symbol = expr[(*n)++];
    
    	switch (*symbol) {
	case '(': return 0;
	case ')': return 1;
	case '+': return 2;
	case '-': return 3;
	case '/': return 4;
	case '*': return 5;
	case '%': return 6;
	case ' ': return 7;
	default: return 8;
	}
}

void print_token(int t){
	switch (t) {
	case 0: printf("( "); break;
	case 1: printf(") "); break;
	case 2: printf("+ "); break;
	case 3: printf("- "); break;
	case 4: printf("/ "); break;
	case 5: printf("* "); break;
	case 6: printf("% "); break;
	case 7: printf("eos "); break;
	default: printf("\n "); return(0);
	}
}
void print_stack(){

}
void postfix(void) {
	char symbol;
	int token;
	int n = 0;
	top = 0;
	stack[0] = 7; // 스택의 바닥에 공백(eos)를 넣는다.
	for (token = get_token(&symbol, &n); token != 7; token = get_token(&symbol, &n))
	{
		if (token == 8) printf("%c ", symbol);
		else if (token == 1) {  // 오른쪽 괄호 만나면 스택에서 모두 pop..
			while (stack[top] != 0) {
				print_token(pop());
				//print_stack();
			}	
			pop();
			//print_stack();
		}
		else { // 연산자들의 우선 순위 비교..
			while (isp[stack[top]] >= icp[token]) {
				print_token(pop());
				//print_stack(pop());
			}
			push(token);
			//print_stack(push(token));
		}
	}
	while ((token = pop()) != 7)
		print_token(token);
	printf(" \n");

}

int main()
{
	strcpy(expr, "3+(2+4)/4 ");// 입력의 마지막에 공백(eos)을 둔다.
	postfix();
	strcpy(expr, "a+b*c-d ");
	postfix();
}
    
}