[자료구조] postfix evaluation

#include<stdio.h>
#include<string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100
typedef enum
{
	open_b, close_b, plus, minus, times, divide, mod, eos, operand
}priority;
int stack[STACK_SIZE];
char expr[EXPR_SIZE];
int pos = 0;
char sym;
int sym_type; //연산자를 연산하기 위한 변수
int top = -1;
int eval_postfix();
void push(int item);
int pop();
char read_item();

void main(void)
{
	strcpy(expr, "936+5-/7*64-*");
	eval_postfix();
}
int eval_postfix()
{
	char sym; //read_item 함수에서 반환한 값을 받을 변수
	int op1, op2; //연산 시 두 개의 피연산자 pop하므로 두 개의 변수
	sym = read_item(); //read_item 함수에서 스택에 저장된 문자를 읽어서 해당 문자에 따라 sym_type을 구조체에서 정의한 숫자로 매치한 후 해당 문자 반환
	while (sym_type != eos) //문자열의 끝(eos)가 아닌 동안 반복
	{
		if (sym_type == operand) //피연산자면 
			push(sym - '0'); //숫자로 바꿔서 push한다. 문자 - 문자를 하면 내부적으로 아스키 코드로 변환되어 원하는 원래 숫자값 얻음
		else //연산자면 스택의 두 피연산자를 해당 연산자로 연산하고 연산 결과값을 스택에 push
		{
			op2 = pop();
			op1 = pop();
			switch (sym_type)
			{
			case plus: push(op1 + op2); break;
			case minus:push(op1 - op2); break;
			case times:push(op1*op2); break;
			case divide:push(op1 / op2); break;
			case mod:push(op1%op2); break;

			}
		}
		sym = read_item(); //한 번 끝나면 또 읽는다.
	}
	return pop(); //연산이 모두 끝났으므로 최종 결과값을 스택에서 pop
}
void print_stack()
{
	int i;

	for (i = 0; i <= top; i++)
	{
		printf("%d ", stack[i]);
	}
	printf("\n");
}
void push(int item)
{
	if (top >= STACK_SIZE - 1)
	{
		printf("stack full\n");
		return;
	}
	stack[++top] = item;
	print_stack();
}
int pop()
{
	if (top < 0)
	{
		printf("sack empty\n");
		return -999;
	}
	return stack[top--]; //마지막에 최종 결과값을 리턴하므로 필요
}
char read_item()
{
	char sym;
	sym = expr[pos++]; //sym에 넣고 pos 증가시켜서 다시 read_item 함수 불렀을 때 다음 문자 읽을 수 있도록 함

	switch (sym)
	{
	case '(':sym_type = open_b; break;
	case ')':sym_type = close_b; break;
	case '+':sym_type = plus; break;
	case '-':sym_type = minus; break;
	case '*':sym_type = times; break;
	case '/':sym_type = divide; break;
	case '%':sym_type = mod; break;
	case '\0':sym_type = eos; break;
	default:sym_type = operand; break;
	}
	return sym; //sym 리턴해서 eval_postfix 함수의 sym에 전달
}

pripory 열거형으로 입력의 종류를 선언함.

switch 함수 통해 expr 배열에 저장된 postfix 문자열의 한 문자를 구분할 때,

sym_type에 priority 열거형에 지정된 숫자로 저장해서

eval_postfix 함수의 while문에서 eos인지 아닌지, if문에서 operand면 push하게 하고,

operator면 스택의 두 operand를 pop해서 sym_type 통해 연산 후 결과값을 다시 push한다.

 

스택이므로, push와 pop 함수는 스택의 코드와 같다.

이번에는 마지막 스택에 저장된 값은 최종 결과값이므로 스택에서 pop하는데,

return pop();을 한다. 따라서 pop 함수에는 결과값을 리턴해야 하므로 return stack[top--]; 문장이어야 한다.

(그냥 스택이었으면 return하지 않고 그냥 stack[top--];하면 됐다.)