스택 자료구조의 활용 - 후위표기식

후위표기식은 수식을 표현하는 한 방법이다. 일반적으로 우리가 쓰는 표기식은 중위표기식, 즉 이항연산자를 두 개의 피연산자 가운데 쓰는 방법인데, 이것은 사람이 보기에 편리하지만 컴퓨터가 수식을 계산하기에는 매우 불편한 형태다. 그 이유는 우리가 수식을 계산할 때 사용하는 순서를 보면 알 수 있다.

7 + 3 * (5 - 2) + 4

이러한 수식을 계산하기 위해서 우리는 우선순위를 고려해야 한다. 즉 +보다 *가 우선순위가 높고 괄호는 가장 먼저 해야 한다. 그러므로 5-2가 먼저 계산된 후 3*3을 계산하고 그 다음에 7+9를 계산해야 한다. 이 때 수식을 왼쪽부터 차례로 읽어가면서 이러한 순서를 판단하여 계산하려면 매우 복잡한 코드가 필요하다.

이 문제를 해결하기 위해 조상 프로그래머들이 발견한 방법이 후위표기식이다. 이것은 피연산자 뒤에 연산자를 쓰는 방법이다. 이 때 문제를 단순하게 하기 위해 모든 연산자는 이항연산자라고 가정하자. 위의 수식은 후위표기식으로 바꾸면 다음과 같다.

7 3 5 2 - * + 4 +

이렇게 바꿔두면 모든 연산자는 항상 앞의 두 개 값을 이용해 계산하면 된다. -는 5와 2를 이용해서 계산하고 *는 3과 -의 결과를 이용해 계산한다. 또한 앞의 +는 7와 *의 결과를 가지고 계산하게 된다. 이 때 연산자를 계산하기 위해 값을 스택에 넣고 팝을 통해 피연산자를 꺼내면 된다. 이 과정을 다음과 같이 표시할 수 있다. (나누기 연산을 포함하기 위해 스택에 푸시되는 값을 double 타입으로 했다.

남은입력				스택				동작
7 3 5 2 - * + 4 +
3 5 2 - * + 4 +			7.0				push(7)
5 2 - * + 4 +			7.0 3.0				push(3)
2 - * + 4 +			7.0 3.0 5.0			push(5)
- * + 4 +			7.0 3.0 5.0 2.0			push(2)
* + 4 +				7.0 3.0 3.0			pop(b); pop(a); push(a - b);
+ 4 +				7.0 9.0				pop(b); pop(a); push(a * b);
4 +				7.0 9.0 16.0			pop(b); pop(a); push(a + b);
+				16.0 4.0			push(4)
				20.0				pop(b); pop(a); push(a + b);

즉 숫자면 push하고 연산자를 만나면 두 개를 pop해서 연산한 결과를 push한다. 이와 같이 동작하도록 프로그램을 작성하면 다음과 같다. 종료를 위해 끝에 "end"를 넣게 했고, 입력은 정수와 사칙연산만 가능한 것으로 보았다.

int main(void)
{
	stack_t stack;
	char token[10];
	double num, a, b;
	init_stack(&stack);
	while (1) {
		scanf_s("%s", token, 10);  // 공백 기준으로 한 단어씩 읽음
		if (strcmp(token, "end") == 0)  // 종료조건
			break;
		if (token[0] >= '0' && token[0] <= '9') {  // 숫자면
			num = atoi(token);
			push(&stack, num);
		}
		else {
			b = pop(&stack);
			a = pop(&stack);
			switch (token[0]) {  // 사칙연산만 가능
			case '+':push(&stack, a + b); break;
			case '-':push(&stack, a - b); break;
			case '*':push(&stack, a * b); break;
			case '/':push(&stack, a / b); break;
			default:break;					
			}
		}
	}
	printf("결과 = %.2f", pop(&stack));
}

이 프로그램에서 다음과 같은 형태로 출력하도록 바꾸어보자. 입력에 대해 동작을 수행한 후 스택의 상태를 출력해 주면 된다. (while 문의 끝에서 호출함)

스택의 상태를 출력하게 하기 위해 앞글에서 살펴본 print_stack이라는 함수를 이용하였다.