19-3-나.스택을 이용한 계산기

수식의 계산

컴퓨터는 계산을 하는 기계이므로 당연히 복잡한 수식도 계산할 수 있다. 이때 계산식은 사람으로부터 주어지는데 키보드로 입력된 문자열에서 숫자와 연산자를 추출해서 계산해야 하는 경우가 많다. 복잡한 수식 문자열을 수치로 변환해서 계산하는 실습을 해 보자.

가장 간단한 수식으로 "1+2"가 주어졌다고 해 보자. 이 수식을 풀려면 atoi 등의 함수로 숫자 1 과 2를 추출하고 덧셈 연산자 +를 추출하여 양변의 수를 산술적으로 더해 3이라는 결과를 만들면 된다. 문자열을 순서대로 읽으려면 포인터로 왼쪽부터 문자들을 스캔해야 하는데 이 정도 수식이라면 어렵지 않게 계산할 수 있다. 조금 더 복잡한 "1+2*3" 연산식은 우선 순위를 고려해야 하므로 생각처럼 쉽지 않다. 정답은 7이되 문자열을 순서대로 읽으면서 계산하는 단순한 방법을 사용하면 9라는 오답이 나올 수도 있다.

그렇다면 더 복잡한 식 "23+35*8-(4+2)/3"을 보자. 연산 순위도 고려해야 하고 두 자리수 이상도 있고 강제로 순위를 바꾸는 괄호까지 있어 문자열 스캔 정도 수준으로는 엄두가 나지 않을 것이다. 이런 복잡한 수식을 풀려면 약간의 발상 전환이 필요하다.

TextCalc

문자열 형태로 주어진 수식을 계산하는 알고리즘은 많이 개발되어 있는데 여기서는 스택을 이용해서 문제를 풀어 보도록 하자. 일단 전체 소스를 보인다.

예 제 : TextCalc

#include <Turboc.h>

#include <math.h>

char *cStack;

int cSize;

int cTop;

void cInitStack(int aSize)

{

cSize=aSize;

cStack=(char *)malloc(cSize*sizeof(char));

cTop=-1;

}

void cFreeStack()

{

free(cStack);

}

BOOL cPush(char data)

{

if (cTop < cSize-1) {

cTop++;

cStack[cTop]=data;

return TRUE;

} else {

return FALSE;

}

}

char cPop()

{

if (cTop >= 0) {

return cStack[cTop--];

} else {

return -1;

}

}

double *dStack;

int dSize;

int dTop;

void dInitStack(int aSize)

{

dSize=aSize;

dStack=(double *)malloc(dSize*sizeof(double));

dTop=-1;

}

void dFreeStack()

{

free(dStack);

}

BOOL dPush(double data)

{

if (dTop < dSize-1) {

dTop++;

dStack[dTop]=data;

return TRUE;

} else {

return FALSE;

}

}

double dPop()

{

if (dTop >= 0) {

return dStack[dTop--];

} else {

return -1;

}

}

int GetPriority(int op)

{

switch (op) {

case '(':

return 0;

case '+':

case '-':

return 1;

case '*':

case '/':

return 2;

case '^':

return 3;

}

return 100;

}

void MakePostfix(char *Post, const char *Mid)

{

const char *m=Mid;

char *p=Post,c;

cInitStack(256);

while (*m) {

// 숫자 - 그대로 출력하고 뒤에 공백 하나를 출력한다.

if (isdigit(*m)) {

while (isdigit(*m) || *m=='.') *p++=*m++;

*p++=' ';

} else

// 연산자 - 스택에 있는 자기보다 높은 연산자를 모두 꺼내 출력하고 자신은 푸시한다.

if (strchr("^*/+-",*m)) {

while (cTop!=-1 && GetPriority(cStack[cTop]) >= GetPriority(*m)) {

*p++=cPop();

}

cPush(*m++);

} else

// 여는 괄호 - 푸시한다.

if (*m=='(') {

cPush(*m++);

} else

// 닫는 괄호 - 여는 괄호가 나올 때까지 팝해서 출력하고 여는 괄호는 버린다.

if (*m==')') {

for (;;) {

c=cPop();

if (c=='(') break;

*p++=c;

}

m++;

} else {

m++;

}

}

// 스택에 남은 연산자들 모두 꺼낸다.

while (cTop != -1) {

*p++=cPop();

}

*p=0;

cFreeStack();

}

double CalcPostfix(const char *Post)

{

const char *p=Post;

double num;

double left,right;

dInitStack(256);

while (*p) {

// 숫자는 스택에 넣는다.

if (isdigit(*p)) {

num=atof(p);

dPush(num);

for(;isdigit(*p) || *p=='.';p++) {;}

} else {

// 연산자는 스택에서 두 수를 꺼내 연산하고 다시 푸시한다.

if (strchr("^*/+-",*p)) {

right=dPop();

left=dPop();

switch (*p) {

case '+':

dPush(left+right);

break;

case '-':

dPush(left-right);

break;

case '*':

dPush(left*right);

break;

case '/':

if (right == 0.0) {

dPush(0.0);

} else {

dPush(left/right);

}

break;

case '^':

dPush(pow(left,right));

break;

}

}

// 연산 후 또는 연산자가 아닌 경우 다음 문자로

p++;

}

}

if (dTop != -1) {

num=dPop();

} else {

num=0.0;

}

dFreeStack();

return num;

}

double CalcExp(const char *exp,BOOL *bError=NULL)

{

char Post[256];

const char *p;

int count;

if (bError!=NULL) {

for (p=exp,count=0;*p;p++) {

if (*p=='(') count++;

if (*p==')') count--;

}

*bError=(count != 0);

}

MakePostfix(Post,exp);

return CalcPostfix(Post);

}

void main()

{

char exp[256];

BOOL bError;

double result;

char *p=strchr("^*/+-",NULL);

strcpy(exp,"2.2+3.5*4.1");printf("%s = %.2f\n",exp,CalcExp(exp));

strcpy(exp,"(34+93)*2-(43/2)");printf("%s = %.2f\n",exp,CalcExp(exp));

strcpy(exp,"1+(2+3)/4*5+2^10+(6/7)*8");printf("%s = %.2f\n",exp,CalcExp(exp));

for (;;) {

printf("수식을 입력하세요(끝낼 때 0) : ");

gets(exp);

if (strcmp(exp,"0")==0) break;

result=CalcExp(exp,&bError);

if (bError) {

puts("수식의 괄호짝이 틀립니다.");

} else {

printf("%s = %.2f\n",exp,result);

}

}

}

실행 결과는 다음과 같다. 몇 개의 예제 수식을 계산하여 출력하고 사용자로부터 입력받은 수식도 계산할 수 있다.

2.2+3.5*4.1 = 16.55

(34+93)*2-(43/2) = 232.50

1+(2+3)/4*5+2^10+(6/7)*8 = 1038.11

수식을 입력하세요(끝낼 때 0) : (1+2)*3

(1+2)*3 = 9.00

수식을 입력하세요(끝낼 때 0) : (((2-1)*3)+1)^2+5

(((2-1)*3)+1)^2+5 = 21.00

표기식 변환을 위해서 문자열 스택이 필요하고 수식 계산을 위해서 실수형 스택이 필요해 각 타입별도 두 개의 스택을 만들었다. cStack과 dStack은 저장하는 데이터의 타입이 다를 뿐 동작하는 방식은 앞에서 만든 정수형 스택과 동일하다. 타입이 다르다고 해서 함수를 완전히 새로 만들어야 하는 것이 마음에 안드는데 C++에서는 이 문제를 해결하는 템플릿이라는 멋진 방법이 있다.

후위 표기법

우리가 수식을 표기할 때 사용하는 표기법을 중위 표기법(Infix Notation)이라고 하는데 연산자가 가운데 오고 피연산자를 연산자의 양쪽에 쓰는 방식이다. 예를 들어 A와 B를 더한다면 A+B로 표기하는 형식이다. 수학에서 이 방법을 사용하고 일상 생활에서도 흔히 사용되므로 이런 표기법은 사람이 보기에는 좋지만 기계가 계산하기는 어렵다. 중위식이 어려운 이유는 연산 순위를 지정하는 괄호가 반드시 필요하기 때문인데 2+(3*4)와 (2+3)*4가 다르게 계산된다. 중위식외에도 연산자의 위치에 따라 다음 두 가지 방법을 더 생각할 수 있다.

▶ 전위식(Prefix Notation) : 연산자가 앞쪽에 오고 피연산자가 뒤에 온다. +AB

▶ 후위식(Postfix Notatio) : 피연산자가 앞쪽에 오고 연산자가 뒤에 온다. AB+

중위식에 비해 동사와 목적어의 순서가 다르다. 전위식과 후위식은 연산 우선 순위를 지정하는 괄호가 필요없다. 왜냐하면 중위식을 전, 후위식으로 바꿀 때 연산자의 위치에 따라 미리 연산 순위를 적용할 수 있기 때문이다. 예를 들어 중위식 A*B+C는 연산 순위에 따라 두 가지 경우가 있는데 이를 전,후위식으로 바꾸면 다음과 같아진다.

중위식	전위식	후위식
(A*B)+C	+*ABC	AB*C+
A*(B+C)	*A+BC	ABC+*

연산자의 등장 순서가 곧 연산 순위이므로 괄호가 필요없다. 그래서 왼쪽에서 오른쪽으로 읽으면서 순서대로 연산하기만 하면 된다. 두 방법중에서는 후위식이 조금 더 쉬운데 피연산자를 구해 놓고 연산자가 나올 때마다 미리 조사한 피연산자를 셈하면 된다.

후위식 변환

후위식이 계산에 아무리 편리하다 하더라도 사람이 후위식으로 입력할 수는 없다. 사람은 오랫동안 중위식만 읽어왔기 때문에 후위식은 사람의 생리와는 도무지 맞지 않다. 그래서 중위식으로 입력된 연산식을 프로그램이 후위식으로 바꾸어 연산해야 한다. 중위식을 후위식으로 바꾸는 절차는 다음과 같다.

① 모든 연산문을 우선 순위에 맞게 괄호를 전부 둘러싼다. 중위식은 괄호가 없으면 어떤 식이 먼저인지 알 수 없으므로 각 부분 연산식에 괄호가 있어야 한다.

② 연산자를 자신이 속한 괄호 바깥으로 보낸다. 즉, 두 피연산자 사이에 있는 연산자를 바로 뒤쪽으로 보내는 것이다.

③ 후위식으로 바꾸면 이제 괄호는 필요가 없으므로 모두 제거한다.

A - B * C + D - E / F 중위식을 이 공식대로 후위식으로 바꿔 보자. 우선 순위에 따라 모든 연산식을 괄호로 싸면 (((A - (B * C)) + D) - (E / F)) 이런 수식이 얻어진다. 그리고 연산자를 뒤쪽으로 보낸 후 괄호를 제거하면 후위식이 완성된다.

결과로 나온 "ABC*-D+EF/-"가 후위식이며 이 식에 연산 순위가 이미 다 고려되어 있으므로 괄호는 필요치 않다. 괄호는 중위식의 우선 순위를 명확히 하기 위해 잠시 필요할 뿐이다. 이렇게 변환한 후 앞쪽부터 순서대로 읽으면서 연산을 수행하면 된다.

스택을 이용한 후위식 변환

문자열을 바로 조작하여 후위식으로 변환하는 방법은 직관적이고 쉽기는 하지만 중위식의 괄호가 완전해야 한다는 제약 조건이 있어 현실적으로 사용하기는 어렵다. 사용자는 뻔한 수식에 대해서는 괄호를 쓰지 않으므로 괄호를 싸는 것도 프로그램이 직접 해야 하는 부담이 있다. 스택을 이용한 후위식 변환은 이에 비해 괄호가 완전하지 않고 일부 생략되어 있더라도 내부적인 우선 순위 규칙에 따라 후위식으로 변환 가능하다.

다음은 스택을 이용하여 후위식으로 변환하는 절차이다. 중위식을 입력 문자열로 사용하고 별도의 후위식 버퍼를 준비한 후 왼쪽에서 순서대로 읽으면서 공식대로 후위식 버퍼로 출력하면 된다. 중위식 형태의 문자열을 후위식 문자열로 바꾸는 것이다.

① 숫자를 만나면 버퍼로 바로 출력한다. 숫자를 구성하는 연속된 문자를 모두 추출해서 하나의 수치값을 만들어야 하는데 정수이면 연속되는 아라비아 숫자를 출력하고 실수일 경우 소수점 문자(.)도 같이 출력해야 한다. 그리고 이어지는 다른 피연산자와의 구분을 위해 공백을 하나 삽입한다. 중위식은 피연산자들 사이에 연산자가 있지만 후위식은 피연산자가 동시에 둘 이상 연속으로 나올 수 있으므로 구분을 위한 공백이 필요하다.

② 연산자를 만나면 스택을 검사하여 자신보다 우선 순위가 높은 연산자를 모두 꺼내 출력한다. 예를 들어 *가 스택에 이미 들어가 있는 상태에서 +연산자를 만났다면 *가 먼저 연산될 수 있도록 한다. 그리고 자기 자신을 스택에 푸시하여 저장한다. 연산자는 일단 스택에 저장되어 차례를 기다려야 하는데 자신보다 낮은 연산자나 닫는 괄호, 또는 수식의 끝일 때 꺼내진다.

③ 여는 괄호를 만나면 스택에 푸시한다. 여는 괄호는 닫는 괄호가 부분 수식의 시작점을 찾기 위해, 그리고 2번 규칙에서 높은 우선 순위의 연산자를 어디까지 찾을 것인가를 결정하기 위해 필요하다.

④ 닫는 괄호를 만나면 여는 괄호가 나올 때까지 스택에 쌓여 있는 모든 연산자를 꺼내 출력한다. 괄호안에 있는 식은 우선 연산되어야 하므로 다음 차례를 기다릴 필요없이 즉시 연산해야 한다. 양쪽 괄호는 우선 순위 지정을 위함 임무를 마쳤으므로 버퍼로 보낼 필요가 없다. 닫는 괄호는 단순히 무시하고 스택에 저장된 여는 괄호는 빼서 버린다. 중위식에서는 괄호가 연산 순위 지정을 위해 필요하지만 후위식에서는 필요하지 않다.

⑤ 중위식이 끝날 때까지 ①~④의 과정을 계속 반복한다. 모든 과정을 마친 후 스택에 남아 있는 연산자를 차례대로 꺼내 버퍼로 출력한다. 남아 있는 연산자들은 우선 순위가 느린 연산자들이므로 제일 뒤쪽에 붙여야 한다.

연산 우선 순위

괄호는 우선 순위를 지정하는 역할을 하므로 괄호가 있으면 괄호의 안쪽을 우선적으로 계산해야 한다. 그러나 괄호가 없는 수식에 대해서는 미리 정한 연산 순위 규칙에 따라 연산자를 배치하여 후위식으로 변환해야 한다. 후위식 변환에서 사용하는 연산 순위는 다음과 같은데 우선 순위가 높을수록 먼저 계산된다. 사칙 연산과 누승 정도만 포함했는데 그 외의 연산자도 물론 포함시킬 수 있다.

연산자	우선 순위
(	0
+, -	1
*, /	2
^(누승)	3

+. - 보다는 *, /의 순위가 높고 *, /보다는 ^의 우선 순위가 높은데 이는 수학적 정의와도 일치한다. 그런데 괄호의 우선 순위가 가장 낮게 설정되어 있는 점은 상식과 일치하지 않는데 그 이유는 ②번 규칙이 제대로 동작하기 위해서이다. 연산자를 만날 때 우선 순위가 높은 연산자를 스택에서 먼저 꺼내도록 되어 있는데 여는 괄호의 왼쪽에 있는 연산자까지는 볼 필요가 없다.

예를 들어 2^(3*4+5)에서 ^이 스택에 먼저 들어가고 다음으로 (, *가 들어가는데 +를 만났을 때 *는 우선적으로 꺼내야 하지만 괄호 바깥의 ^은 아직 꺼낼 필요가 없는 것이다. 스택에서 여는 괄호를 만났다는 것은 현재 연산자가 괄호안에 있다는 뜻이고 괄호의 안은 바깥보다 항상 우선이므로 괄호를 만나면 자신보다 높은 연산자를 더 이상 찾지 않아도 된다.

이 규칙을 만족하기 위해 괄호의 우선 순위를 가장 낮게 설정하여 어떤 연산자든 괄호를 만날때 스택 팝을 중지하도록 했다. 사실 괄호는 연산자가 아니며 우선 순위를 지정하는 구두점일 뿐이므로 그 자체에는 연산 순위가 없다고 볼 수 있다. 다만 다른 연산자들의 우선 순위 구분을 위해 임시적으로 스택에 푸시될 뿐이며 괄호는 ③, ④번 규칙에 의해 따로 관리된다. 예제에서는 GetPriority 함수로 연산 순위를 조사하는데 단순한 switch문이다.

변환의 예

변환 규칙이 무척 복잡한데 구체적인 예를 들어 보자. 다음은 아주 간단한 중위식 A+B*C를 후위식으로 바꾸는 절차이다. 종이에 입력 버퍼, 출력 버퍼, 그리고 스택을 그려 놓고 직접 변환해 보아라.

입력 문자	출력 버퍼	스택	설명
A	A		숫자는 바로 출력
+	A	+	연산자는 스택에 저장
B	AB	+	숫자는 바로 출력
*	AB	+*	스택에 푸시. +가 *보다 낮으므로 꺼내지 않음
C	ABC	+*	숫자는 바로 출력
NULL	ABC*+		스택에서 역순으로 꺼냄.

+ 연산자를 만났을 때 이 연산자를 출력 버퍼로 바로 보내지 않는 이유는 오른쪽의 피연산자(이 경우 B)를 먼저 버퍼로 보내야 하기 때문인데 후위식은 피연산자 둘이 나와야 연산자가 올 수 있다. 그래서 자신은 우변 피연산자가 나올 때까지 잠시 대기해야 하는데 그 장소가 바로 스택이다. B를 만났을 때 +를 버퍼로 보내지 않는 이유는 B가 단독으로 +의 우변인지 아니면 B를 포함한 연산식이 +의 우변인지를 아직 확신하지 못하기 때문이다. 이 시점까지 읽은 A+B가 연산 순위에 맞는지 아닌지는 뒤쪽을 좀 더 읽어 봐야 한다.

* 연산자도 마찬가지로 아직 우변이 없으므로 스택에 대기하는데 이때 앞쪽의 연산자 +보다는 자신이 우선 순위가 높으므로 앞의 +를 꺼낼 필요가 없다. 이 단계에서 곱셈 연산이 먼저 되어야 앞쪽의 덧셈 연산이 가능하다는 것을 알게 된 것이다. 즉, *는 자신의 우변을 기다리고 있는 상황이고 +는 자신의 우변인 * 연산식을 기다리고 있는 상황이다. 다음으로 C를 출력 버퍼로 보내고 입력 수식은 끝난다.

끝으로 스택에 대기하고 있던 연산자를 역순으로 팝해서 출력버퍼로 보낸다. 역순이므로 *가 먼저 팝되어 B와 C를 곱하는 연산을 하게 되며 다음으로 +가 팝되어 A와 B*C를 더하게 된다. 다음은 비슷한 수식 A*B+C를 후위식으로 바꾸어 보자.

입력 문자	출력 버퍼	스택	설명
A	A		숫자는 바로 출력
*	A	*	연산자는 스택에 저장
B	AB	*	숫자는 바로 출력
+	AB*	+	+보다 *가 높으므로 *는 먼저 꺼낸다.
C	AB*C	+	숫자는 바로 출력
NULL	AB*C+		남은 연산자를 꺼내 출력한다.

앞의 수식과는 연산 순위가 다른데 *가 먼저 오고 뒤에 +가 온다. A가 출력 버퍼로 가고 다음으로 연산자 *는 스택으로, B가 출력 버퍼로 먼저 나간다. 이 상태에서 +를 만났을 때 앞쪽에 대기하고 있던 *를 바로 출력하는데 +보다는 *가 더 우선 순위가 높기 때문이다. 즉, +를 만났을 때 이미 구해 놓은 두 개의 피연산자 A, B가 *의 피연산자임을 결정할 수 있으므로 먼저 연산되도록 하는 것이다.

+ 연산자는 뒤쪽에 자신보다 늦은 연산자가 없으므로 수식이 끝날 때까지 스택에 대기하다가 마지막으로 팝되어 제일 뒤에 붙는다. 그래서 +는 전체 연산식에서 가장 우선 순위가 느리다. 다음은 괄호가 있는 (A+B)*C식의 경우를 보자.

입력 문자	출력 버퍼	스택	설명
(		(	여는 괄호는 바로 푸시
A	A	(	숫자는 바로 출력
+	A	(+	+ 푸시. (보다 +가 높으므로 팝할 필요없다.
B	AB	(+	숫자는 바로 출력
)	AB+		여는 괄호를 만날 때까지 모든 연산자 출력
*	AB+	*	* 푸시
C	AB+C	*	숫자는 바로 출력
NULL	AB+C*		남은 연산자를 꺼내 출력한다.

뒤쪽의 *가 +보다 우선 순위가 높지만 닫는 괄호에 의해 괄호 안쪽의 모든 연산자가 강제 출력되므로 이 경우는 +가 먼저 연산된다. 괄호는 안쪽의 연산자를 우선적으로 꺼냄으로서 괄호 바깥의 연산자보다 먼저 연산되도록 하는 역할을 한다.

MakePostfix

예제에서 중위식을 후위식으로 변환하는 작업은 MakePostfix라는 함수로 구현하고 있는데 이 함수가 하는 일은 앞에서 설명한 공식을 그대로 코드로 옮긴 것 뿐이다. 변환에 필요한 스택을 생성하고 입력 버퍼 포인터 m을 뒤로 진행시키면서 만나는 문자별로 규칙에 따라 처리한다.

숫자는 있는 그대로 출력 버퍼로 보내되 연속되는 숫자를 모두 보내야 한다. 이때 숫자를 구성하는 문자로는 아라비아 숫자와 소수점이 있다. 숫자를 구성하는 모든 문자를 출력 버퍼로 보낸 후 공백 하나를 더 보낸다. 그래야 다음 피연산자와 자신을 구분할 수 있다.

연산자를 만나면 자신보다 높은 우선 순위의 연산자를 모두 꺼내 출력하되, 단 스택 언더플로우는 점검해야 한다. 스택에 대기중인 연산자가 더 없으면 이때는 아무 것도 꺼낼 필요가 없다. 그리고 자기 자신도 다음 차례를 위해 스택에 푸시된다.

여는 괄호는 단순히 푸시만 하고 닫는 괄호는 여는 괄호가 나올 때까지 모든 연산자를 팝해서 출력하고 여는 괄호는 버린다. 여는 괄호와 대응되는 닫는 괄호 사이에 있는 모든 연산자는 괄호 바깥의 연산자와는 상관없이 우선적으로 연산되도록 하는 것이다. 이 과정을 입력 문자열의 끝까지 반복 처리하고 스택에 남아 있는 연산자를 팝해서 출력하면 후위식이 완성된다. 마지막으로 후위식 문자열 끝에 널 종료 문자를 붙이고 임시 스택을 파괴한 후 리턴했다.

후위식 계산

만들어진 후위식은 이제 기계적으로 연산하기만 하면 된다. 피연산자가 먼저 나오고 연산자가 나오므로 왼쪽부터 순서대로 읽어 나가다가 연산자를 만났을 때 앞쪽 두 피연산자를 연산하면 된다. 가장 간단한 식 AB+의 경우 A, B를 만날 때 이 숫자들을 기억해 두었다가 +를 만났을 때 A와 B를 더하면 된다. 그러나 이것보다는 조금 더 복잡한데 피연산자가 다른 연산식일 수도 있기 때문이다.

예를 들어 ABC+*의 경우 +는 B와 C를 더하지만 *는 A와 B+C를 곱해야 하므로 B+C의 연산 결과를 기다린 후 그 결과와 A를 연산해야 한다. 더 복잡한 수식의 경우는 연산 결과끼리 연산하거나 최종 피연산자를 구하기 전에 선행되어야 할 연산이 3중, 4중으로 중첩될 수 있다. 그래서 연산자를 읽는 족족 연산을 할 수 없고 앞쪽부터 중간 결과를 저장해 가면서 연산을 해 와야 한다.

이때 앞쪽 연산의 결과를 저장하는 곳이 바로 스택이다. 스택을 이용해서 후위식을 연산하는 절차는 비교적 간단하다. 괄호가 없으므로 왼쪽부터 순서대로 후위식을 읽어 오면 숫자이거나 연산자밖에 없으며 이외의 문자로는 숫자끼리 구분을 위해 삽입된 공백밖에 없다. 공백은 단순히 건너 뛰기만 하면 되고 두 경우만 다음과 같이 처리한다.

■ 숫자 : 숫자로 인식되는 부분만큼 읽어서 스택에 푸시한다. atof 함수로 변환하면 숫자로 인정되는 부분까지 자동으로 변환되므로 이 함수로 입력 버퍼를 숫자로 바꿔 푸시하기만 하면 된다. 이렇게 저장된 숫자는 다음 연산자를 만날 때 피연산자로 사용된다. 푸시한 숫자는 건너 뛰어 입력 버퍼의 다음 위치에 맞추어 놓는다.

■ 연산자 : 스택에 있는 피 연산자를 두 개 꺼내 연산한다. 입력 버퍼의 앞쪽부터 순서대로 읽어 왔다면 스택에는 최소한 두 개 이상의 숫자가 들어 있으므로 이 값을 꺼내 연산하기만 하면 된다. 먼저 꺼내는 값이 우변이고 나중에 꺼내는 값이 좌변인데 덧셈, 곱셈은 순서가 중요하지 않지만 뺄셈, 나눗셈은 순서를 잘 지켜 연산해야 한다. 연산된 결과는 다른 연산식의 피연산자가 될 수 있으므로 다시 스택에 밀어 넣어야 한다.

이런 식으로 만나는 숫자와 연산자를 순서대로 처리하다가 널 종료 문자를 만났을 때 스택에 마지막으로 남아 있는 값이 최종 연산 결과이다. 우선 순위가 제일 늦은 연산자가 끝에 남은 두 피연산자를 연산해서 스택에 다시 밀어 놓았을 것이므로 그 결과를 취하면 된다. 특수한 예외로 나누기 연산에서 나누는 수가 0인 경우는 결과를 0으로 정의했다.

이 논리를 구현한 함수가 예제의 CalcPostfix 함수이다. 후위식 연산을 위해서는 중간 과정의 피연산자를 스택에 저장해야 하므로 실수 스택을 만들고 이 스택에 숫자들을 푸시, 팝 하면서 연산했다. 예제의 두 번째 수식 "(34+93)*2-(43/2)"의 후위식 "34 93 + 2 * 43 2 / -"의 연산 과정을 보면 다음과 같다.

입력 버퍼	스택	설명
34	34	숫자 푸시
93	34 93	숫자 푸시
+	127	34+93 연산 후 푸시
2	127 2	숫자 푸시
*	254	127*2 연산 후 푸시
43	254 43	숫자 푸시
2	254 43 2	숫자 푸시
/	254 21.5	43/2 연산 후 푸시
-	232.5	254-21.5 연산 후 푸시
NULL		스택에 남은 232.5를 결과로 취함

숫자는 무조건 푸시하고 연산자를 만날 때마다 피연산자 둘을 연산하기를 끝까지 반복하는 것이다. 단, 특수한 경우로 수식이 빈 문자열일 경우에는 스택에 아무 값도 들어가지 않으므로 0을 리턴하도록 했다. 빈 수식의 결과값은 0으로 계산하는 것이 합당하다.

예제 전체 분석

TextCalc 예제는 상기 분석한 알고리즘대로 중위식을 후위식으로 바꾸고 후위식을 연산하여 결과를 출력한다. 범용적인 연산이 가능하도록 하기 위해 실수를 사용했는데 double형이면 웬만큼 정밀한 연산을 모두 할 수 있다. 만약 정수 연산만 하고 싶다면 dStack을 정수형으로 바꾸고 숫자를 읽어들이는 함수 atof 대신 atoi를 사용하면 된다. 또는 최종 결과 출력문인 printf의 서식을 %.0f로만 바꾸어도 비슷한 효과를 낼 수 있다.

중위식을 후위식으로 바꾸고 연산까지 하려면 번거롭기 때문에 중위식을 전달하면 후위식으로 바꾼 후 연산하는 랩퍼 함수 CalcExp를 작성했다. 이 함수는 연산하기 전에 기본적인 에러 점검을 하는데 괄호의 짝이 맞지 않을 경우 실패를 리턴한다. 실패 리턴값을 받고 싶으면 CalcExp에 BOOL형 변수의 포인터를 전달하여 그 결과를 받을 수 있되 실패 여부에 관심이 없으면 NULL을 전달해도 상관없다.

이 예제는 후위식 변환을 위해 그리고 변환된 후위식 계산을 위해 두 개의 스택을 사용한다. 연산자의 경우 뒤쪽을 더 읽어 봐야 정확한 연산 순위를 알 수 있으므로 자기 차례가 될 때까지 잠시 대기해야 하며 계산식의 경우 부분식의 계산 결과가 이어지는 연산자의 피연산자로 사용되기 위해 임시적으로 저장되어야 한다. 그리고 연산자와 부분식 모두 들어간 역순으로 꺼내야 하므로 스택이 가장 적절한 자료 구조이다.

스택의 크기는 두 경우 모두 256으로 설정했는데 이 크기는 계산을 위해서 아주 충분한 크기라고 할 수 있다. 연산자와 부분식은 나오는 족족 푸시되기만 하는 것이 아니라 차례가 되면 팝되어 빠져 나오므로 256이라는 스택 크기는 처리할 수 있는 최대 연산자 개수가 아니라 최대 중첩 가능 회수가 된다. 아무리 식이 복잡해 봐야 10단계 이상 중첩되는 경우는 거의 없으므로 256정도면 펑펑 남아돌 정도의 크기이다.

이상으로 스택을 이용한 간단한 계산기 예제 제작을 마친다. 알고리즘이 나름대로 복잡해서 되도록 간단하게 만들기 위해 노력했는데 그러다 보니 몇 가지 한계점이 있다. 우선 이항 연산자만을 다룸으로써 - 부호 연산자를 인식하지 않는다. 3 + -2는 1로 계산되어야 하지만 -을 이항 연산자로 인식하므로 틀린 결과가 나올 것이다.

또한 누승 연산자의 경우 우측 우선의 결합 순서를 가지지만 이 예제는 편의상 좌측 우선으로 처리했다. 그래서 두 번 연거푸 누승 연산을 할 경우 수학적인 계산과는 틀린 결과가 나온다. 2^3^4는 왼쪽 우선일 때 8^4으로 4096이지만 오른쪽 우선이면 2^81으로 엄청난 수가 된다.