수식 트리 (ParseTree)의 계산 및 트리 구조 표현

소개글

수식 트리 (ParseTree)의 계산 및 트리 구조 표현에 대한 보고서 자료입니다.

목차

1. 문제제기 :

2. 문제분석 & 문제해결 :
① 트리 구조 정의
② 수식 트리의 생성
③ 노드의 순회
④ 수식의 계산
⑤ 수식트리의 표현

3. 프로그래밍 소스 :

4. 결과화면 :

5. 느낀점 :

본문내용

.
{
cout<data<<" ";
}
void gotoxy(int x, int y)//좌표계 설정 함수
{
COORD Pos = {x , y };
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);
}
void ParseTree::Tree_Print(Node *pNode)//노드를 출력하는 함수
{
if(temp==0)//출력을 처음 시작
{
gotoxy(x,y);//좌표설정. 초기값 x=40, y = 7
cout<<"["<Right->data<<"]";
//헤드노드의 제일 첫 원소부터 출력
temp++;//처음 시작체크 해제
}
if(pNode==Tailnode)//마지막노드까지 갔으면 종료
return;
if(pNode->Left!=Tailnode) //왼쪽을 순회하며 출력
{
x-=15/count;y+=4; //좌표설정. 왼쪽방향으로 x값 감소
gotoxy(x,y);
cout<<"["<Left->data<<"]";//왼쪽 원소 출력
gotoxy(x+15/count/4,y-1);//노선 출력
cout<<"↙";
gotoxy(x+15*2/count/4,y-2);
cout<<"↙";//노선출력
gotoxy(x+15*3/count/4,y-3);
cout<<"↙";
count++;//노선 출력
Tree_Print(pNode->Left);//왼쪽 방향 재귀 순회
count--; //x좌표가 왼쪽으로 몇번 움직였나 확인후
x+=15/count;y-=4;//다시 원위치(가운데로)
}
if(pNode->Right!=Tailnode)//오른족을 순회하며 출력
{
x+=15/count;y+=4;//좌표설정. 오른쪽방향으로 x값 증가
gotoxy(x,y);
cout<<"["<Right->data<<"]";//오른쪽원소 출력
gotoxy(x-15/count/4,y-1); //노선 출력
cout<<"↘";
gotoxy(x-15*2/count/4,y-2);//노선 출력
cout<<"↘";
gotoxy(x-15*3/count/4,y-3);//노선 출력
cout<<"↘";
count++;
Tree_Print(pNode->Right); //오른쪽방향 재귀 순회
count--; //x좌표가 오른쪽으로 몇번 움직였나 확인후
x-=15/count;y-=4;//다시 원위치 (중심으로)
}
if(y>=temp_y) //제일 밑의 노드를 출력했을 때의 좌표 기억
temp_y=y;
gotoxy(0,temp_y+5);
}
int ParseTree::Calculate(Node *pNode)
{
if(pNode == Tailnode)
{
return 0;
}
else if(pNode->Left == Tailnode && pNode->Right ==Tailnode) //이경우 숫자임
{
int i=0;
if (IsNumber(pNode->data[i]))//숫자인경우
{
int num = 0;
while(IsNumber(pNode->data[i]))
//2자리 이상의 숫자인경우에 대해 반복적으로 읽어올수있도록한다.
{
num = num*10 + pNode->data[i] - '0'; //한 자리가 올라갈수록 10배증가후 뒷자리 숫자를 더한다.
//여기서 문자열은 문자형이므로 아스키코드를 빼준다.
i++;//그다음자리를 읽는다.
//그다음자리가 숫자이면 다시 while문으로 들어가고, 아니면 그냥 pass
}
return num;//계산된 num값을 리턴
}
}
else if(IsOperator(pNode->data[0])) //연산자일 경우
{
int operand1 = Calculate(pNode->Left);
//연산자의 왼쪽노드와
int operand2 = Calculate(pNode->Right);
//오른쪽 노드를 계산한 값을 저장
switch(pNode->data[0])//연산자에 따라 분기하여 계산
{
case '+':
return operand1 + operand2;
case '-':
return operand1 - operand2;
case '*':
return operand1 * operand2;
case '/':
if(operand2 == 0)//예외처리
{
cout<<"0으로 나눌 수 없습니다.\n";
return 0;
}
else
{
return operand1 / operand2;
}
}
}
return 0;
}
4. 결과화면 :
계산 결과화면을 위해서 식을 준비하였다.
이와 같은 식을 지난번 postfix프로그램으로 변환하면,
1, 3, +, 20, 2, -, *, 2, 9, * 18, 6, /, / , + 가 된다. 이 후위 표기식을 이번 ParseTree에 입력해보자.
5. 느낀점 :
지금까지의 과제였던 스택이나 큐, 배열 링크드리스트는 사실 조금씩이나마 1학년 때부터 알아왔던 것이었기에 큰 부담은 없었지만, 트리라는 자료구조는 이번이 처음 접하게 되었습니다. 처음에는 낯설고 잘 이해가 되지 않았지만 강의 자료를 잘 참고하였습니다.
식을 전위식이나 후위 식, 중위 식에 대해 모두 가능하게 할 수 도 있었지만 사실상 모두 후위식을 기반으로 만들어야 하기 때문에, 특별한 처리는 생략하고 후위 표기식을 입력받도록 구현하였습니다. 중위 표기식으로부터 생성하는 기능이 반드시 필요하다면, 중위 표기식을 후위표기식으로 변환한 다음에 이 프로그램을 이용하면 되므로 생략하였습니다.
트리를 생성하는 것은 어렵지 않았으나, 2자리수 이상의 경우에 대해서 고려하는 부분이 어려웠습니다. 결국 지난 과제에서 스트링을 숫자로 변환했던 방법을 약간 수정하여 똑같이 적용하였습니다.
트리를 출력하는 것이 가장 어려웠습니다. 어렵다기보단 직접 좌표를 찾고 설정해야 하는 부분이 까다로웠습니다. 축의 높이와 레벨에 따라서 약간씩 꺾이는 경향이 있어서, 약간 보기 불편하더라도 최대한으로 보기 좋게 구현하였습니다.
공부하다보니 트리를 응용하여 여러 가지 정렬 등에 사용될 수 있는 것을 보았는데, 아직은 너무 어려워 보이지만 반드시 넘어야할 산이라면 열심히 해야겠다는 다짐을 하였습니다.

키워드

수식 트리,   Parse Tree,   이진 트리 출력,   후위표기식,   후위표기식 계산