스택의 응용: 후위 표기 수식 계산

• 중위(infix): 연산자가 피연산자 사이에
• 후위(postfix): 연산자가 피연산자 뒤에
• 전위(prefix): 연산자가 피연산자 앞에

인간은 주로 중위표기법을 사용하지만 컴파일러는 후위표기법을 사용한다. 프로그래머가 수식을 중위표기법으로 작성하면 컴파일러는 이를 후위표기법으로 변환한 뒤 스택을 사용해 계산한다.

중위 표기법	전위 표기법	후위 표기법
2+3*4	+2*34	234*+
a*b+5	+*ab5	ab*5+
(1+2)*7	*+127	12+7*

 

중위표기법에서는 먼저 계산할 부분을 나타내기 위해 괄호를 사용해야 하는 데 비해, 후위표기법에서는 괄호가 필요 없다. 또, 이미 식 자체에 우선순위가 표현되어 있어 연산자의 우선순위도 고려할 필요가 없으므로 수식을 읽으면서 바로 계산이 가능하다.

 

후위 표기 수식을 계산하려면, 수식을 왼쪽에서 오른쪽으로 스캔하여 피연산자이면 스택에 저장하고, 연산자이면 필요한 수만큼의 피연산자를 스택에서 꺼내 연산을 실행한 후 연산의 결과를 다시 스택에 저장한다.

 

후위 표기 수식 82/3-32*+을 스택을 이용해 계산하는 경우 스택의 내용은 아래와 같다.

토큰	스택
	[0]	[1]	[2]	[3]	[4]	[5]	[6]
8	8
2	8	2
/	4
3	4	3
-	1
3	1	3
2	1	3	2
*	1	6
+	7

이 후위 표기 수식을 왼쪽에서 오른쪽으로 스캔하면 제일 먼저 8을 만나게 되는데, 8은 피연산자이므로 스택에 삽입된다. 다음에 만나는 피연산자인 2도 마찬가지로 스택에 저장된다. 다음 글자인 /은 나누기 연산자이므로 스택에서 8과 2를 꺼내 나누기 연산을 한 결과인 8/2=4를 스택에 삽입한다. 그 다음 글자인 3은 피연산자이므로 스택에 저장하고, -는 연산자이므로 스택에서 4와 3을 꺼내어 뺄셈 연산을 하고 4-3=1을 스택에 저장한다. 이런 식으로 끝까지 진행하면 결국 스택에는 7이 남게 되고, 이 7이 전체 수식의 결과값이 된다.

 

후위 표기 수식 계산 알고리즘은 아래와 같다.

---

중위표기수식을 후위표기식으로 변환

 

중위 표기법과 후위 표기법은 피연산자의 순서가 동일하지만, 연산자들의 순서가 다르다. 연산자들의 순서는 우선순위에 따라 달라진다. 

중위 표기법	후위 표기법
a+b	ab+
(a+b)*c	ab+c*
a+b*c	abc*+

 

중위 표기 수식을 후위 표기 수식으로 변환하기 위해 입력 수식을 왼쪽에서 오른쪽으로 스캔한다. 피연산자를 만나게 되면 바로 후위 표기 수식에 출력하고, 연산자를 만나면 따로 저장한다. 후위 표기 수식에서는 기본적으로 피연산자들 뒤에 연산자가 나오므로 적절한 위치를 찾을 때까지 출력을 보류해야 하기 때문이다. 

 

a+b를 후위 표기 수식으로 변환한다면 연산자인 a와 b는 스캔된 즉시 출력하고 +는 저장했다 마지막에 출력하면 된다. 하지만 a+b*c를 출력할 때는 저장된 +와 * 중 어떤 것이 먼저 출력될지 결정해야 한다. 기본적으로 가장 나중에 스캔된 연산자가 가장 먼저 출력되어야 하므로(LIFO), 연산자들은 후입선출 구조인 스택에 저장되는 것이 타당하다. 

 

하지만 a*b+c와 같은 수식의 경우, 연산자들의 우선순위를 고려해야 한다. +가 스택에 나중에 삽입되고 먼저 출력되면, +가 *보다 먼저 계산되기 때문이다. 따라서 스택에 존재하는 연산자가 현재 처리 중인 연산자보다 우선순위가 높을 경우, 일단 스택에 있는 연산자들 중에서 우선순위가 높은 연산자들을 먼저 출력한 다음 처리 중인 연산자를 스택에 넣어야 한다. a-b+c와 같은 경우에도 abc+-로 출력한다면 문제가 발생하므로, 우선순위가 같을 때에도 일단 스택 상단의 요소를 꺼내 출력해야 한다.

 

중위 표기 수식에 괄호가 존재할 경우, 왼쪽 괄호는 무조건 스택에 삽입한다. 왼쪽 괄호는 일단 스택에 삽입되면 우선순위가 가장 낮은 연산자로 취급된다. 다음에 만나는 모든 연산자가 스택에 삽입되는 것이다. 오른쪽 괄호를 만나게 되면 왼쪽 괄호가 삭제될 때까지 왼쪽 괄호 위에 쌓여 있는 모든 연산자들을 출력한다.

 

이때까지 설명했던 알고리즘을 의사 코드로 만들면 아래와 같다.

---

프로그램 4.7 후위표기식 계산

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

typedef char element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

void init_stack(StackType* s) {
	s->top = -1;
}
int is_empty(StackType* s) {
	return (s->top == -1);
}
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}
void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;

	}
	else
		s->data[++(s->top)] = item;
}
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[(s->top)--];
}
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[s->top];
}

int eval(char exp[]) {
	int op1, op2, value, i = 0;
	int len = strlen(exp);
	char ch;
	StackType s;

	init_stack(&s);
	for (i = 0; i < len; i++) {
		ch = exp[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
			//입력이 피연산자일 때
			value = ch - '0';
			push(&s, value);
		}
		else {
			//입력이 연산자일 때
			op2 = pop(&s);
			op1 = pop(&s);
			switch (ch) {
			case '+': push(&s, op1 + op2); break;
			case '-': push(&s, op1 - op2); break;
			case '*': push(&s, op1 * op2); break;
			case '/': push(&s, op1 / op2); break;
			}
		}
	}
	return pop(&s);
}

int main(void) {
	int result;
	printf("후위표기식은 82/3-32*+\n");
	result = eval("82/3-32*+");
	printf("결과값은 %d\n", result);
	
	return 0;
}

>>

 

위 코드에서는 피연산자가 한 자리 수라고 가정한다.

여러 문자로 된 숫자를 처리하려면 입력 문자열을 분석하는 별도의 프로그램이 있어야 한다.

 

프로그램 4.8 중위 표기 수식을 후위 표기 수식으로 변환하는 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

typedef char element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

void init_stack(StackType* s) {
	s->top = -1;
}
int is_empty(StackType* s) {
	return (s->top == -1);
}
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}
void push(StackType* s, element item) {
	if (is_full(&s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else
		s->data[++(s->top)] = item;
}
element pop(StackType* s) {
	if (is_empty(&s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[(s->top)--];
}
element peek(StackType* s) {
	if (is_empty(&s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[s->top];
}

//연산자 우선순위 반환 함수
int prec(char op) {
	switch (op) {
	case '(': case ')': return 0;
	case '+': case'-': return 1;
	case '*': case '/': return 2;
	}
	return -1;
}

//중위->후위 변환 함수
void infix_to_postfix(char exp[]) {
	int i = 0;
	char ch, top_op;
	int len = strlen(exp);
	StackType s;

	init_stack(&s);
	for (i = 0; i < len; i++) {
		ch = exp[i];
		switch (ch) {
		case '+': case'-': case '*': case '/':	//연산자일 때
			while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
				printf("%c", pop(&s));
			push(&s, ch);
			break;
		case '(':
			push(&s, ch);
			break;
		case ')':
			top_op = pop(&s);	//왼쪽 괄호를 만날 때까지 출력
			while (top_op != '(') {
				printf("%c", top_op);
				top_op = pop(&s);
			}
			break;
		default:
			printf("%c", ch);
			break;
		}
	}
	while (!is_empty(&s))
		printf("%c", pop(&s));
}

int main(void) {
	char* s = "(2+3)*4+9";
	printf("중위표기수식 %s\n", s);
	printf("후위표기수식 ");
	infix_to_postfix(s);
	printf("\n");
	
	return 0;
}

>>