다음 예제는 19장에서 작성했던 정수형 스택을 클래스로 만든 것이다. 스택을 표현하는데 필요한 정수형 배열과 배열 크기, 스택 포인터 등을 멤버 변수로 포함시키고 Push, Pop 등의 기본 동작은 멤버 함수로 구현했다. 스택을 초기화하는 기능은 생성자에 작성하고 해제하는 코드는 파괴자에 두면 된다.
|
예 제 : iStack |
#include <Turboc.h>
class iStack
{
private:
int *Stack;
int Size;
int Top;
public:
iStack(int aSize) {
Size=aSize;
Stack=(int *)malloc(Size*sizeof(int));
Top=-1;
}
virtual ~iStack() {
free(Stack);
}
virtual BOOL Push(int data) {
if (Top < Size-1) {
Top++;
Stack[Top]=data;
return TRUE;
} else {
return FALSE;
}
}
virtual int Pop() {
if (Top >= 0) {
return Stack[Top--];
} else {
return -1;
}
}
};
void main()
{
iStack iS(256);
iS.Push(7);
iS.Push(0);
iS.Push(6);
iS.Push(2);
iS.Push(9);
printf("%d\n",iS.Pop());
printf("%d\n",iS.Pop());
printf("%d\n",iS.Pop());
printf("%d\n",iS.Pop());
printf("%d\n",iS.Pop());
}
스택이 필요할 때는 iStack 클래스의 인스턴스를 생성하는데 인수로 스택의 크기만 밝히면 나머지 필요한 초기화는 생성자에서 한다. 그리고 Push, Pop 등의 멤버 함수를 호출하여 스택을 편리하게 사용할 수 있다. 다 사용한 스택은 파괴자에서 정리하므로 별도의 해제를 할 필요가 없다.
동작에 필요한 필수 멤버들이 한 클래스에 캡슐화되어 있으므로 확실히 사용하기에는 편리하다. 그러나 아직 타입에 대한 종속성을 해결하지는 못했는데 iStack은 정수형 값만 저장할 수 있을 뿐이며 double이나 char 형을 저장할 수는 없다. 다른 타입에 대한 스택을 만들려면 iStack의 일부를 수정해야 하는데 Stack 멤버의 타입, Push의 인수, Pop의 리턴 타입 정도만 바꾸면 된다. 타입만 변경될 뿐 알고리즘은 동일하므로 템플릿을 사용하면 임의 타입을 지원할 수 있다.
19장에서 실수형 스택과 문자형 스택을 사용하여 수식을 계산하는 TextCalc 예제를 만들어 본 적이 있는데 잘 동작하기는 하지만 똑같은 논리를 사용하는 스택이 두 카피 존재한다는 점이 무척 불합리해 보인다. 단지 타입만 다를 뿐인데 이것들을 하나로 합칠 수가 없는 것이다. 이렇게 되면 코드의 양이 많아지는 것은 물론이고 기능을 확장할 때도 일일이 두 군데를 고쳐야 하므로 유지하기가 아주 어려워진다. 템플릿을 사용하여 스택 하나로 두 가지 타입을 지원하도록 수정해 보자. 먼저 스택 클래스 템플릿을 헤더 파일에 작성한다.
|
예 제 : TStack.h |
template<typename T>
class TStack
{
protected:
T *Stack;
int Size;
int Top;
public:
TStack(int aSize) {
Size=aSize;
Stack=(T *)malloc(Size*sizeof(T));
Top=-1;
}
virtual ~TStack() {
free(Stack);
}
virtual BOOL Push(T data) {
if (Top < Size-1) {
Top++;
Stack[Top]=data;
return TRUE;
} else {
return FALSE;
}
}
virtual T Pop() {
return Stack[Top--];
}
virtual int GetTop() { return Top; }
virtual T GetValue(int n) { return Stack[n]; }
};
템플릿 기반으로 수정했으므로 이름을 TStack이라고 지었으며 스택에 저장할 타입을 인수열로 전달받는다. 멤버 함수의 논리는 앞의 iStack 예제와 동일하며 int가 들어가야 할 위치에 T가 대신 들어갔을 뿐이다. 몇 가지 차이점도 있는데 우선 에러 처리를 위해 Top 위치를 조사하는 GetTop 멤버 함수와 우선 순위 조사를 위해 지정한 위치의 값을 삭제하지는 않고 읽기만 하는 GetValue 함수가 추가되었다.
그리고 Pop 함수의 에러 처리 코드가 삭제되었는데 임의의 타입에 대해 동작하기 위해서는 -1을 리턴하는 단순한 방법을 쓸 수 없기 때문이다. -1이라는 특이값은 수치형에만 존재하므로 스택에 객체를 저장할 때는 에러를 처리하는 다른 방법이 필요하다. 스택에 아무 것도 없는 상태에서 pop을 호출하는 것은 분명한 논리적 에러이므로 assert를 쓰는 것이 가장 합리적이다. 이 템플릿이 제대로 동작하는지 계산기 예제를 만들어 보자.
|
예 제 : TextCalcTemplate |
#include <Turboc.h>
#include <math.h>
#include "TStack.h"
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;
TStack<char> cS(256);
while (*m) {
// 숫자 - 그대로 출력하고 뒤에 공백 하나를 출력한다.
if (isdigit(*m)) {
while (isdigit(*m) || *m=='.') *p++=*m++;
*p++=' ';
} else
// 연산자 - 스택에 있는 자기보다 높은 연산자를 모두 꺼내 출력하고 자신은 푸시한다.
if (strchr("^*/+-",*m)) {
while (cS.GetTop()!=-1 && GetPriority(cS.GetValue(cS.GetTop())) >=
GetPriority(*m)) {
*p++=cS.Pop();
}
cS.Push(*m++);
} else
// 여는 괄호 - 푸시한다.
if (*m=='(') {
cS.Push(*m++);
} else
// 닫는 괄호 - 여는 괄호가 나올 때까지 팝해서 출력하고 여는 괄호는 버린다.
if (*m==')') {
for (;;) {
c=cS.Pop();
if (c=='(') break;
*p++=c;
}
m++;
} else {
m++;
}
}
// 스택에 남은 연산자들 모두 꺼낸다.
while (cS.GetTop() != -1) {
*p++=cS.Pop();
}
*p=0;
}
double CalcPostfix(const char *Post)
{
const char *p=Post;
double num;
double left,right;
TStack<double> dS(256);
while (*p) {
// 숫자는 스택에 넣는다.
if (isdigit(*p)) {
num=atof(p);
dS.Push(num);
for(;isdigit(*p) || *p=='.';p++) {;}
} else {
// 연산자는 스택에서 두 수를 꺼내 연산하고 다시 푸시한다.
if (strchr("^*/+-",*p)) {
right=dS.Pop();
left=dS.Pop();
switch (*p) {
case '+':
dS.Push(left+right);
break;
case '-':
dS.Push(left-right);
break;
case '*':
dS.Push(left*right);
break;
case '/':
if (right == 0.0) {
dS.Push(0.0);
} else {
dS.Push(left/right);
}
break;
case '^':
dS.Push(pow(left,right));
break;
}
}
// 연산 후 또는 연산자가 아닌 경우 다음 문자로
p++;
}
}
if (dS.GetTop() != -1) {
num=dS.Pop();
} else {
num=0.0;
}
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)*4
(1+2+3)*4 = 24.00
중위식을 후위식으로 변환하는 MakePostfix 함수는 문자형의 스택이 필요하므로 TStack<char> 타입의 cS를 256크기로 선언해서 사용한다. 이 선언문에 의해 컴파일러는 char 타입에 대한 스택 클래스를 구체화할 것이다. cS가 지역변수이므로 함수가 종료될 때 자동으로 파괴되며 따라서 별도의 정리 코드를 작성할 필요가 없다.
후위식을 연산하는 CalcPostfix 함수는 연산 과정의 중간값 저장을 위해 실수형 스택이 필요하다. 그래서 TStack<double> 타입의 dS를 선언해서 사용하고 있다. 두 함수가 각각 타입이 다른 스택을 만들어 사용하지만 클래스가 템플릿으로 선언되어 있으므로 아무 문제가 없다. 필요하다면 얼마든지 많은 타입에 대해 스택을 만들어 쓸 수 있을 것이다.