Chapter 06. 계산기 프로그램의 구현 (4)

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

다음과 같은 후위 표기법의 수식을 계산할 알고리즘을 어떻게 구현할 것인지 고민해 봅니다.

 

3 2 4 * + 

 

저는 후위 표기법의 계산 방법이 꽤 복잡할 것으로 생각했습니다. 하지만 그렇지 않았습니다. 후위 표기법의 수식을 계산하는 알고리즘은 스택을 이용하면 정말 간단하게 구현할 수 있습니다. 그 알고리즘은 다음과 같습니다.

1. 후위 표기법의 수식에서 데이터를 하나씩 읽어 들인다.
2. 읽어 들인 데이터가 피연산자라면 이를 스택에 저장한다.
3. 읽어 들인 데이터가 연산자라면 스택에서 두 개의 피연산자를 꺼내어 이를 계산한 후, 결과를 스택에 저장한다.
4. 읽어 들일 데이터가 없으면 스택에 남은 데이터를 결과로 반환한다.

 

위의 내용이 알고리즘의 전부입니다. 정말 간단합니다. 어떻게 이런 알고리즘이 수행되는지 과정을 설명하겠습니다.

후위 표기법의 수식
3	2	4	*	+

숫자는 전부 스택에 저장하므로 알고리즘을 진행하면 다음과 같이 됩니다.

후위 표기법의 수식
			*	+

4

2

3

이제 '*'연산자가 나왔으므로 스택에서 두 개의 값을 꺼내어 곱셈 연산을 수행하고, 결과를 스택에 저장합니다. 이때 스택에서 먼저 꺼낸 피연산자가 뒤에 오도록, 나중에 꺼낸 피연산자가 앞에 오도록 연산을 수행합니다.

 

무슨 말이냐. 지금 스택에는 4, 2, 3이 저장되어 있습니다. 여기서 두 개의 피연산자를 꺼내면 4가 먼저 나오고 그다음 2가 나옵니다. 이때 4 * 2로 계산하면 안 됩니다. 계산 순서는 2 * 4가 되어야 합니다. 물론 곱셈에서는 피연산자의 위치가 바뀌어도 상관없지만 뺄셈이나 나눗셈의 경우에는 다릅니다. 알고리즘을 진행하면 다음과 같이 됩니다.

후위 표기법의 수식
				+

8

3

'+' 연산자가 나왔으므로 스택에서 두 개의 피연산자를 꺼내고 연산을 수행합니다. 역시 8 + 3이 아닌, 3 + 8로 연산을 수행해야 합니다. 알고리즘을 진행하면 다음과 같이 됩니다.

후위 표기법의 수식

11

더 이상 읽을 데이터가 없으므로 결과로 스택에 남아 있는 값인 11을 반환합니다.

 

이제 지금까지 설명한 알고리즘을 바탕으로, 후위 표기법의 수식을 계산하여 그 결과를 반환하는 다음의 함수를 정의해 보겠습니다.

int EvalRPNExp(char exp[])
{
	....
}

위 함수는 후위 표기법의 수식을 저장하고 있는 exp를 인자로 받아서 계산 결과를 반환합니다. 위 함수를 한 번 직접 구현해 보길 권합니다.

 

EvalRPNExp 함수를 구현하면 다음과 같습니다.

int EvalRPNExp(char exp[])
{
	Stack stack;          //스택 생성
	StackInit(&stack);    //스택 초기화

	int expLen = strlen(exp);
	char tok;
	int res;

	int i;
	for (i = 0; i < expLen; i++)
	{
		tok = exp[i];
		if (isdigit(tok))               //tok가 10진수라면
		{
			Push(&stack, tok - '0');    //문자인 tok를 숫자로 변환하여 스택에 저장
		}
		else
		{
			int first = Pop(&stack);     //스택에서 첫 번째 값 꺼내기
			int second = Pop(&stack);    //스택에서 두 번째 값 꺼내기

			switch (tok)                 //연산자에 맞게 연산하기
			{
			case '+':
				res = second + first;    //피연산자의 위치 주의
				break;
				
			case '-':
				res = second - first;
				break;

			case '*':
				res = second * first;
				break;

			case '/':
				res = second / first;
				break;

			default:
				printf("등록되지 않은 연산입니다.\n");
				exit(1);
			}

			Push(&stack, res);    //계산 결과를 스택에 저장하기
		}
	}

	res = Pop(&stack);
	FreeStack(&stack);

	return res;
}

계산을 double형으로 해야 제대로 된 계산기 프로그램이 완성되겠지만 우선은 int형으로 계산을 수행하도록 합니다. 현재 과정에서 double형으로 계산을 수행하는 것은 중요하지 않기 때문입니다.

 

이제 위 함수의 선언과 정의를 적절하게 다음과 같은 두 개의 파일로 분리하고,

• PostCalculator.h    EvalRPNExp 함수의 선언
• PostCalculator.c    EvalRPNExp 함수의 정의

 

적절한 main함수를 구성하여 실행결과를 확인하겠습니다.

//PostCalculator.h 헤더 파일로 저장
#ifndef POSTCALCULATOR_H
#define POSTCALCULATOR_H

int EvalRPNExp(char exp[]);

#endif

//PostCalculator.c 소스 파일로 저장
#include "PostCalculator.h"
#include "LLBStack.h"
#include <string.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

int EvalRPNExp(char exp[])
{
	Stack stack;          //스택 생성
	StackInit(&stack);    //스택 초기화

	int expLen = strlen(exp);
	char tok;
	int res;

	int i;
	for (i = 0; i < expLen; i++)
	{
		tok = exp[i];
		if (isdigit(tok))               //tok가 10진수라면
		{
			Push(&stack, tok - '0');    //문자인 tok를 숫자로 변환하여 스택에 저장
		}
		else
		{
			int first = Pop(&stack);     //스택에서 첫 번째 값 꺼내기
			int second = Pop(&stack);    //스택에서 두 번째 값 꺼내기

			switch (tok)                 //연산자에 맞게 연산하기
			{
			case '+':
				res = second + first;    //피연산자의 위치 주의
				break;
				
			case '-':
				res = second - first;
				break;

			case '*':
				res = second * first;
				break;

			case '/':
				res = second / first;
				break;

			default:
				printf("등록되지 않은 연산입니다.\n");
				exit(1);
			}

			Push(&stack, res);    //계산 결과를 스택에 저장하기
		}
	}

	res = Pop(&stack);
	FreeStack(&stack);

	return res;
}

//main.c 소스 파일로 저장
#include "InfixToPostfix.h"
#include "PostCalculator.h"
#include <stdio.h>

int main(void)
{
	char exp1[] = "1+2+3";
	char exp2[] = "(1+2)*3";
	char exp3[] = "((1-2)+3)*(5-2)";

	ConvToRPNExp(exp1);
	ConvToRPNExp(exp2);
	ConvToRPNExp(exp3);

	printf("%s = %d\n", exp1, EvalRPNExp(exp1));
	printf("%s = %d\n", exp2, EvalRPNExp(exp2));
	printf("%s = %d\n", exp3, EvalRPNExp(exp3));

	return 0;
}

/*
실행결과

12+3+ = 6
12+3* = 9
12-3+52-* = 6

*/