스택 자료구조의 활용 - 후위표기식
후위표기식은 수식을 표현하는 한 방법이다. 일반적으로 우리가 쓰는 표기식은 중위표기식, 즉 이항연산자를 두 개의 피연산자 가운데 쓰는 방법인데, 이것은 사람이 보기에 편리하지만 컴퓨터가 수식을 계산하기에는 매우 불편한 형태다. 그 이유는 우리가 수식을 계산할 때 사용하는 순서를 보면 알 수 있다.
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이라는 함수를 이용하였다.