중위, 후위, 전위 수식 표기법 (Infix, Postfix, Prefix)

중위 표기법 (Infix)

- 연산자가 피연산자 사이에 온다.

- 각 연산자별로 우선 순위가 있으며, 괄호를 사용하여 우선 순위를 바꿀 수 있다.

- 사람이 이해하기는 쉬우나 연산 순서가 복잡하여 프로그래밍이 어렵다.

 

후위 표기법 (Postfix)

- 연산자가 피연산자 맨 뒤에 온다.

- 연산자의 우선 순위가 없고 괄호를 사용하지 않는다.

- 왼쪽에서 오른쪽 방향으로 계산하므로 프로그래밍이 쉽다.

 

ex) 5 + 9 * 7 (Infix)

>> 5 9 7 * + (Postfix)

 

---

 

후위 수식 (Postfix) 계산 알고리즘

1. 수식을 왼쪽에서 오른쪽으로 스캔한다.

2. 수식에서 들어온 입력이 피연산자이면 스택에 넣는다.

3. 입력이 연산자이면 스택에서 피연산자 2개를 꺼내서 계산한 후 결과 값을 다시 스택에 넣는다.

 

---

 

후위 수식의 평가 (Postfix Evaluation)

후위 수식( 5 7 * 9 + 3 4 / - )을 스택을 이용하여 계산하는 과정을 표로 나타내었다.

 

입력	STACK			TOP
	[0]	[1]	[2]
5 7 * 9 + 3 4 / -	5 5 35 35 44 44 44 44 44	7   9   3 3 0	4	0 1 0 1 0 1 2 1 0

 

---

 

후위 수식 평가 프로그램 (Postfix Evaluation Program)

// 수식 평가 스택
#include <stdio.h>
#include <string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100
#pragma warning(disable : 4996)

typedef enum
{
	open_b, close_b, plus, minus, times, divide, mod, eos, operand
} priority;				// 0, 1, 2, 3, 4, 5, 6, 7, 8
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 print_stack();

void main()
{
	strcpy(expr, "57*9+34/-");
	eval_postfix();
}

int eval_postfix()
{
	char sym;
	int op1, op2;
	sym = read_item();			// 수식 심볼 전달
	while (sym_type != eos)
	{
		if (sym_type == operand)
			push(sym - '0');	// 아스키코드로 자동 변환
		else
		{						// 연산자
			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);
			}
		}
		sym = read_item();
	}
	return pop();	// 최종 결과값 전달
}

void push(int item)
{
	if (top >= STACK_SIZE - 1)
	{
		printf("stack full");
		return;
	}
	stack[++top] = item;
	print_stack();
}

int pop()
{
	if (top < 0)
	{
		printf("stack empty");
		return -999;
	}
	return stack[top--];
}

void print_stack()
{
	int i;
	for (i = 0; i <= top; i++)
		printf("%d ", stack[i]);
	printf("\n");
}

// 심볼 입력
char read_item()
{
	char sym;
	sym = expr[pos++];	// 현재 pos 위치의 심볼을 저장 후 한 칸 이동
	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;
	}
	return sym;
}

 

---

 

중위 수식(Infix)에서 후위 수식(Postfix)으로 변환

1. 수식 안의 모든 연산을 괄호로 묶는다.

2. 연산자의 위치를 피연산자들의 뒤로 옮긴 뒤에, 옮겨준 괄호 안의 ')'를 지운다.

3. 모든 작업이 끝난 뒤에 더 지울 ')'가 남아있지 않으면 남아있는 '('를 모두 지운다. 

 

 ex) a / b - c + d * e - a * c

>> ( ( ( ( a / b ) - c ) + ( d * e ) ) - ( a * c ) )

>> ( ( ( ( a b / c - ( d e * + ( a c * -

>> a b / c - d e * + a c * -

 

---

 

중위 수식(Infix)에서 후위 수식(Postfix)으로 변환 알고리즘

1. 입력이 피연산자이면 그대로 출력한다.

2. 입력의 우선 순위가 스택 top의 연산자보다 높거나 (입력 > stack_top), 스택이 비어 있으면, 입력을 스택에 넣는다.

3. 스택의 연산자 우선 순위가 입력보다 작거나 높으면 (입력 <= stack_top), 스택 연산자(stack_top)를 pop하고 입력을 스택에 넣는다.

4. 입력이 '(' 이면, ')'이 들어올 때까지 다음 연산자를 위의 규칙을 따라서 스택에 넣는다.

5. 입력이 ')'이면, '('이 나올 때까지 스택에서 계속 연산자를 pop해서 출력하고 '('은 출력하지 않고 버린다.

6. 입력이 문자열의 끝(eos)이면, 스택의 모든 연산자를 꺼내서 출력한다.

 

---

 

중위 수식(Infix)에서 후위 수식(Postfix)으로 변환 프로그램

 

// 중위 수식을 후위 수식으로 변환

#include <stdio.h>
#include <ctype.h>
#define STACK_SIZE 100
#pragma warning(disable : 4996)

char token_stack[STACK_SIZE];
int token_top = -1;
void infix_to_postfix();
int precedence(char op);
void push_token(char sym);
char pop_token();

void main()
{
	infix_to_postfix();
}

void infix_to_postfix()
{
	char expr[50], sym, token;
	int pos = 0;

	printf("Enter the expression :: ");
	scanf("%s", expr);

	while ((token = expr[pos++]) != '\0')
	{
		if (isalnum(token))	// 알파벳 또는 숫자
			printf("%c ", token);
		else if (token == '(')
			push_token(token);
		else if (token == ')')	// '('이 나올 때까지 모든 연산자 출력
		{
			while ((sym = pop_token()) != '(')
				printf("%c ", sym);
		}
		else
		{
			while (precedence(token_stack[token_top]) >= precedence(token) && token_top != -1)
				printf("%c ", pop_token());
			push_token(token);
		}
	}
	while (token_top != -1)	// 남아 있는 모든 원소 출력
		printf("%c ", pop_token());
}

int precedence(char op)
{
	if (op == '(')
		return 0;
	if (op == '+' || op == '-')
		return 1;
	if (op == '*' || op == '/' || op == '%')
		return 2;
}

void push_token(char sym)
{
	if (token_top < STACK_SIZE)
		token_stack[++token_top] = sym;
	else
		printf("token stack full\n");
}

char pop_token()
{
	if (token_top >= 0)
		return token_stack[token_top--];

	printf("token stack empty \n");
	return ' ';
}