<수식 트리 구현>
[ExpressionTree.h]
/*
* 비선형 자료구조 - 수식 트리 (이진 트리의 응용)
* 파일명: ExpressionTree.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자:
* 버전 내용: 수식 트리 구현 및 계산 결과 프로그램 작성
* 이전 버전 내용:
*/
#ifndef __EXPRESSION_TREE_H__
#define __EXPRESSION_TREE_H__
#include "BinaryTree.h" // 수식 트리도 이진 트리의 일종.
BTreeNode* MakeExpTree(char exp[]); // 수식 트리 구성
int EvaluateExpTree(BTreeNode* bt); // 수식 트리를 이용한 계산
// 생성한 수식 트리가 맞게 되었는가 확인하기 위해 만든 출력부
void ShowPrefixTypeExp(BTreeNode* bt); // 전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode* bt); // 중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode* bt); // 후위 표기법 기반 출력
#endif
[ExpressionTree.c]
/*
* 비선형 자료구조 - 수식 트리 (이진 트리의 응용)
* 파일명: ExpressionTree.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자:
* 버전 내용: 수식 트리 구현 및 계산 결과 프로그램 작성
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // 문자열 관련 함수 사용을 위해 헤더파일 포함
#include <ctype.h> // isdigit() 함수 사용을 위해 헤더파일 포함
#include "BinaryTree.h" // 수식 트리도 이진 트리의 일종.
#include "ListBaseStack.h" // 스택을 이용하여 수식 트리를 구성하므로 헤더파일 포함
// 수식 트리 구성
BTreeNode* MakeExpTree(char exp[])
{
Stack stack; // 트리 생성에 사용할 스택 선언
BTreeNode* pnode; // 트리를 만들 노드 선언
int expLen = strlen(exp); // 입력받은 수식의 길이
int i; // 반복문에 사용될 변수 i
StackInit(&stack); // 스택 초기화
for (i = 0; i < expLen; i++) // 수식을 토큰으로 나눠가며 수식 트리 생성
{
pnode = MakeBTreeNode(); // 수식 트리를 구성할 새로운 노드를 생성
if (isdigit(exp[i])) // 만약 피연산자라면
SetData(pnode, exp[i] - '0'); // 노드의 데이터를 저장, exp[i]는 문자이므로 문자 '0'과의 차가 실제 정수값이다.
else // 연산자라면
{
MakeRightSubTree(pnode, SPop(&stack)); // 스택에서 먼저 나온 노드(또는 서브트리)를 오른쪽 자식 노드로 연결하고
MakeLeftSubTree(pnode, SPop(&stack)); // 그 다음 스택에서 나온 노드(또는 서브트리)를 왼쪽 자식 노드로 연결한다.
SetData(pnode, exp[i]); // 그리고 연산자를 노드에 저장한다.
}
SPush(&stack, pnode); // 위의 과정을 거치고 나면 스택에 집어넣는다.
}
return SPop(&stack); // 마지막으로 수식트리가 완성이 되면 최상단 루트 노드의 주소값을 반환한다.
}
int EvaluateExpTree(BTreeNode* bt) // 수식 트리를 이용한 계산
{
int op1, op2; // 피연산자1, 2로 사용할 변수
if (GetLeftSubTree(bt) == NULL && GetRightSubTree(bt) == NULL) // 단말노드, 즉 피연산자라면
return GetData(bt); // 피연산자 값을 반환한다
op1 = EvaluateExpTree(GetLeftSubTree(bt)); // 왼쪽 서브트리의 계산된 값을 피연산자로 받는다 (재귀)
op2 = EvaluateExpTree(GetRightSubTree(bt)); // 오른쪽 서브트리의 계산된 값을 피연산자로 받는다 (재귀)
switch (GetData(bt)) // 연산자의 종류에 따라 계산
{
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
}
return 0;
}
void ShowNodeData(int data)
{
if (0 <= data && data <= 9)
printf("%d ", data);
else
printf("%c ", data);
}
// 생성한 수식 트리가 맞게 되었는가 확인하기 위해 만든 출력부
void ShowPrefixTypeExp(BTreeNode* bt) // 전위 표기법 기반 출력
{
PreorderTraversal(bt, ShowNodeData); // 전위 순회, 그리고 순회하면서 하는 동작은 ShowNodeData.
}
void ShowInfixTypeExp(BTreeNode* bt) // 중위 표기법 기반 출력
{
if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
return;
if (bt->left != NULL || bt->right != NULL) // 연산자를 대상으로 왼쪽이나 오른쪽에 피연산자가 있을 때, 괄호'('를 열고
printf("(");
// 재귀를 이용하는 것이 핵심이다!
ShowInfixTypeExp(bt->left); // 1) 첫 번째 피연산자 출력
ShowNodeData(bt->data); // 2) 연산자 출력
ShowInfixTypeExp(bt->right); // 3) 두 번째 피연산자 출력
if (bt->left != NULL || bt->right != NULL) // 연산자를 대상으로 왼쪽이나 오른쪽에 피연산자가 있으면 괄호 ')'를 닫는다.
printf(")");
}
void ShowPostfixTypeExp(BTreeNode* bt) // 후위 표기법 기반 출력
{
PostorderTraversal(bt, ShowNodeData); // 전위 순회, 그리고 순회하면서 하는 동작은 ShowNodeData.
}
[ExpressionTreeMain.c]
/*
* 비선형 자료구조 - 수식 트리 (이진 트리의 응용)
* 파일명: ExpressionTree.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자:
* 버전 내용: 수식 트리 구현 및 계산 결과 프로그램 작성
* 이전 버전 내용:
*/
#include <stdio.h>
#include "ExpressionTree.h"
int main()
{
char exp[] = "12+7*"; // 후위 표기법의 수식
BTreeNode* eTree = MakeExpTree(exp); // 수식 트리 생성
printf("전위 표기법의 수식: ");
ShowPrefixTypeExp(eTree); // 수식 트리를 입력받아 전위 표기법 수식으로 출력
printf("\n");
printf("중위 표기법의 수식: ");
ShowInfixTypeExp(eTree); // 수식 트리를 입력받아 중위 표기법으로 출력
printf("\n");
printf("후위 표기법의 수식: ");
ShowPostfixTypeExp(eTree); // 수식
printf("\n");
printf("연산의 결과: %d\n", EvaluateExpTree(eTree));
return 0;
}
수식 트리 역시 이진 트리의 일종이다.
그래서 이전에 이진 트리를 구현하는데 사용했던 코드를 그대로 사용하면 쉽게 만들 수 있다.
[BinaryTree.h], [BinaryTree.c]는 이전에 이진 트리에서 다뤘던 코드를 그대로 가져다 썼으므로 생략.
그리고 수식의 계산을 위해 스택이 필요하다.
스택도 이전에 구현한 [ListBaseStack.h], [ListBaseStack.c]를 그대로 가져다 썼으므로 생략.
안그래도 코드 블록에 주석이 덕지덕지 붙어서 글이 길어졌으니 추가된 코드만 수록하겠다.
[수식 트리란?]
일반적으로 사람들은 중위 표기식과 같은 (1+2)*3과 같은 수식을 봤을 때 자연스럽게 계산을 할 수 있다.
하지만, 컴파일러는 이걸 그대로 해석을 할 수가 없다.
그래서 컴파일러가 위의 수식을 실행할 수 있도록 사람이(정확히 말하면 프로그래머가) 방법을 결정한다.
그리고 그 방법을 토대로 컴파일러에게 인식시켜서 수식을 해석할 수 있도록 한다.
여기서 사용되는 것이 수식 트리라는 자료구조다.
수식 트리를 이용하면 컴파일러의 수식 해석이 좋아지게 된다.
그래서 컴파일러에서는 수식의 이해를 위해 수식을 수식 트리로 바꿔서 표현하게 된다.
중위 표기법이나 후위 표기법과 같이 수식 트리 역시 수식을 표기하는 하나의 방법이다.
이 수식 트리를 가지고 전위 순회를 하면 전위 표기법처럼 된다.
후위 순회를 하면 후위 표기법이 되며, 중위 순회를 하면 중위 표기법처럼 된다.
위에서 구현한 것은 후위 표기법의 수식을 받아서 수식 트리로 바꾸고, 이를 계산하는 프로그램을 구현한 것이다.
[후위 표기법 수식을 기반으로 수식 트리 구성하기]
후위 표기법으로 수식 트리를 만들기 위해서는 스택이 필요하다.
우선 수식을 하나하나 토큰으로 쪼개서 연산자와 피연산자를 구분한다.
그리고 다음과 같은 일련의 과정을 거쳐서 만들어진다.
1) 토큰이 피연산자라면 무조건 스택으로 들어간다.
2) 연산자라면, 스택에서 Pop을 2회 수행한다.
먼저 나온 피연산자는 연산자의 오른쪽, 다음에 나온 피연산자는 왼쪽 자식 노드로 연결한다.
3) 자식 노드를 연결해서 만들어진 트리의 루트 노드 주소값을 스택에 집어 넣는다.
4) 1~3)의 과정을 반복해서 최종적으로 생성된 수식 트리는 스택으로 들어간 마지막 트리다.
[전위, 중위, 후위 순회]
수식 트리의 장점은 순회 방식에 따라 수식을 전위, 중위, 후위 표기법의 수식으로 다양하게 출력이 가능하다.
이 부분은 이전에 이진 트리 구현에서 만들었던 함수를 그대로 이용하여 순회를 시키면 수식 출력이 간편하게 된다.
참고로 중위 순회 부분은 괄호를 포함한 로직이 추가가 되어 있다.
[수식 트리의 계산]
이전의 이진트리에서도 했었던 이야기지만, 이진 트리는 재귀적인 구조를 띈다.
그렇기 때문에 계산에서도 재귀적인 구조는 그대로 적용이 된다.
그래서 연산 과정 역시 재귀적으로 해결해나가면 되는 부분이다.
왼쪽 연산자는 왼쪽 서브트리를 타고 들어가서 계속 계산하며 올라오면 된다.
오른쪽 연산자도 마찬가지로 오른쪽 서브트리를 타고 들어가서 계속 계산하며 올라오면 된다.
그러다보면 최종적으로 루트 노드까지 와서 마지막으로 계산하고 결과를 확인할 수 있다.
그리고 재귀의 탈출 조건으로는 왼쪽과 오른쪽 자식이 없는 경우, 다시 말해서 단말 노드일 때다.
이 때는 데이터를 반환하고 return하는 것으로 재귀의 탈출 조건을 세웠다.
나름대로 정리한다고 정리는 했지만 아직도 제대로 정리가 안된 느낌이다.
비선형 자료구조부터는 확실히 리스트나 스택, 큐와는 성격이 다른 부분이 커서 그렇다고 생각한다.
구현하면서 작성한 소스코드에 주석을 하나하나 달아놓았다.
나중에 복습하면서 다시 보면 금방 떠올릴 수 있게 최대한 상세하게 적어두었다.
<수식 트리 구현>
[ExpressionTree.h]
/*
* 비선형 자료구조 - 수식 트리 (이진 트리의 응용)
* 파일명: ExpressionTree.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자:
* 버전 내용: 수식 트리 구현 및 계산 결과 프로그램 작성
* 이전 버전 내용:
*/
#ifndef __EXPRESSION_TREE_H__
#define __EXPRESSION_TREE_H__
#include "BinaryTree.h" // 수식 트리도 이진 트리의 일종.
BTreeNode* MakeExpTree(char exp[]); // 수식 트리 구성
int EvaluateExpTree(BTreeNode* bt); // 수식 트리를 이용한 계산
// 생성한 수식 트리가 맞게 되었는가 확인하기 위해 만든 출력부
void ShowPrefixTypeExp(BTreeNode* bt); // 전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode* bt); // 중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode* bt); // 후위 표기법 기반 출력
#endif
[ExpressionTree.c]
/*
* 비선형 자료구조 - 수식 트리 (이진 트리의 응용)
* 파일명: ExpressionTree.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자:
* 버전 내용: 수식 트리 구현 및 계산 결과 프로그램 작성
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // 문자열 관련 함수 사용을 위해 헤더파일 포함
#include <ctype.h> // isdigit() 함수 사용을 위해 헤더파일 포함
#include "BinaryTree.h" // 수식 트리도 이진 트리의 일종.
#include "ListBaseStack.h" // 스택을 이용하여 수식 트리를 구성하므로 헤더파일 포함
// 수식 트리 구성
BTreeNode* MakeExpTree(char exp[])
{
Stack stack; // 트리 생성에 사용할 스택 선언
BTreeNode* pnode; // 트리를 만들 노드 선언
int expLen = strlen(exp); // 입력받은 수식의 길이
int i; // 반복문에 사용될 변수 i
StackInit(&stack); // 스택 초기화
for (i = 0; i < expLen; i++) // 수식을 토큰으로 나눠가며 수식 트리 생성
{
pnode = MakeBTreeNode(); // 수식 트리를 구성할 새로운 노드를 생성
if (isdigit(exp[i])) // 만약 피연산자라면
SetData(pnode, exp[i] - '0'); // 노드의 데이터를 저장, exp[i]는 문자이므로 문자 '0'과의 차가 실제 정수값이다.
else // 연산자라면
{
MakeRightSubTree(pnode, SPop(&stack)); // 스택에서 먼저 나온 노드(또는 서브트리)를 오른쪽 자식 노드로 연결하고
MakeLeftSubTree(pnode, SPop(&stack)); // 그 다음 스택에서 나온 노드(또는 서브트리)를 왼쪽 자식 노드로 연결한다.
SetData(pnode, exp[i]); // 그리고 연산자를 노드에 저장한다.
}
SPush(&stack, pnode); // 위의 과정을 거치고 나면 스택에 집어넣는다.
}
return SPop(&stack); // 마지막으로 수식트리가 완성이 되면 최상단 루트 노드의 주소값을 반환한다.
}
int EvaluateExpTree(BTreeNode* bt) // 수식 트리를 이용한 계산
{
int op1, op2; // 피연산자1, 2로 사용할 변수
if (GetLeftSubTree(bt) == NULL && GetRightSubTree(bt) == NULL) // 단말노드, 즉 피연산자라면
return GetData(bt); // 피연산자 값을 반환한다
op1 = EvaluateExpTree(GetLeftSubTree(bt)); // 왼쪽 서브트리의 계산된 값을 피연산자로 받는다 (재귀)
op2 = EvaluateExpTree(GetRightSubTree(bt)); // 오른쪽 서브트리의 계산된 값을 피연산자로 받는다 (재귀)
switch (GetData(bt)) // 연산자의 종류에 따라 계산
{
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
}
return 0;
}
void ShowNodeData(int data)
{
if (0 <= data && data <= 9)
printf("%d ", data);
else
printf("%c ", data);
}
// 생성한 수식 트리가 맞게 되었는가 확인하기 위해 만든 출력부
void ShowPrefixTypeExp(BTreeNode* bt) // 전위 표기법 기반 출력
{
PreorderTraversal(bt, ShowNodeData); // 전위 순회, 그리고 순회하면서 하는 동작은 ShowNodeData.
}
void ShowInfixTypeExp(BTreeNode* bt) // 중위 표기법 기반 출력
{
if (bt == NULL) // 만약 공집합 노드(NULL)이라면? 재귀의 탈출 조건이 된다.
return;
if (bt->left != NULL || bt->right != NULL) // 연산자를 대상으로 왼쪽이나 오른쪽에 피연산자가 있을 때, 괄호'('를 열고
printf("(");
// 재귀를 이용하는 것이 핵심이다!
ShowInfixTypeExp(bt->left); // 1) 첫 번째 피연산자 출력
ShowNodeData(bt->data); // 2) 연산자 출력
ShowInfixTypeExp(bt->right); // 3) 두 번째 피연산자 출력
if (bt->left != NULL || bt->right != NULL) // 연산자를 대상으로 왼쪽이나 오른쪽에 피연산자가 있으면 괄호 ')'를 닫는다.
printf(")");
}
void ShowPostfixTypeExp(BTreeNode* bt) // 후위 표기법 기반 출력
{
PostorderTraversal(bt, ShowNodeData); // 전위 순회, 그리고 순회하면서 하는 동작은 ShowNodeData.
}
[ExpressionTreeMain.c]
/*
* 비선형 자료구조 - 수식 트리 (이진 트리의 응용)
* 파일명: ExpressionTree.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-24
* 이전 버전 작성 일자:
* 버전 내용: 수식 트리 구현 및 계산 결과 프로그램 작성
* 이전 버전 내용:
*/
#include <stdio.h>
#include "ExpressionTree.h"
int main()
{
char exp[] = "12+7*"; // 후위 표기법의 수식
BTreeNode* eTree = MakeExpTree(exp); // 수식 트리 생성
printf("전위 표기법의 수식: ");
ShowPrefixTypeExp(eTree); // 수식 트리를 입력받아 전위 표기법 수식으로 출력
printf("\n");
printf("중위 표기법의 수식: ");
ShowInfixTypeExp(eTree); // 수식 트리를 입력받아 중위 표기법으로 출력
printf("\n");
printf("후위 표기법의 수식: ");
ShowPostfixTypeExp(eTree); // 수식
printf("\n");
printf("연산의 결과: %d\n", EvaluateExpTree(eTree));
return 0;
}
수식 트리 역시 이진 트리의 일종이다.
그래서 이전에 이진 트리를 구현하는데 사용했던 코드를 그대로 사용하면 쉽게 만들 수 있다.
[BinaryTree.h], [BinaryTree.c]는 이전에 이진 트리에서 다뤘던 코드를 그대로 가져다 썼으므로 생략.
그리고 수식의 계산을 위해 스택이 필요하다.
스택도 이전에 구현한 [ListBaseStack.h], [ListBaseStack.c]를 그대로 가져다 썼으므로 생략.
안그래도 코드 블록에 주석이 덕지덕지 붙어서 글이 길어졌으니 추가된 코드만 수록하겠다.
[수식 트리란?]
일반적으로 사람들은 중위 표기식과 같은 (1+2)*3과 같은 수식을 봤을 때 자연스럽게 계산을 할 수 있다.
하지만, 컴파일러는 이걸 그대로 해석을 할 수가 없다.
그래서 컴파일러가 위의 수식을 실행할 수 있도록 사람이(정확히 말하면 프로그래머가) 방법을 결정한다.
그리고 그 방법을 토대로 컴파일러에게 인식시켜서 수식을 해석할 수 있도록 한다.
여기서 사용되는 것이 수식 트리라는 자료구조다.
수식 트리를 이용하면 컴파일러의 수식 해석이 좋아지게 된다.
그래서 컴파일러에서는 수식의 이해를 위해 수식을 수식 트리로 바꿔서 표현하게 된다.
중위 표기법이나 후위 표기법과 같이 수식 트리 역시 수식을 표기하는 하나의 방법이다.
이 수식 트리를 가지고 전위 순회를 하면 전위 표기법처럼 된다.
후위 순회를 하면 후위 표기법이 되며, 중위 순회를 하면 중위 표기법처럼 된다.
위에서 구현한 것은 후위 표기법의 수식을 받아서 수식 트리로 바꾸고, 이를 계산하는 프로그램을 구현한 것이다.
[후위 표기법 수식을 기반으로 수식 트리 구성하기]
후위 표기법으로 수식 트리를 만들기 위해서는 스택이 필요하다.
우선 수식을 하나하나 토큰으로 쪼개서 연산자와 피연산자를 구분한다.
그리고 다음과 같은 일련의 과정을 거쳐서 만들어진다.
1) 토큰이 피연산자라면 무조건 스택으로 들어간다.
2) 연산자라면, 스택에서 Pop을 2회 수행한다.
먼저 나온 피연산자는 연산자의 오른쪽, 다음에 나온 피연산자는 왼쪽 자식 노드로 연결한다.
3) 자식 노드를 연결해서 만들어진 트리의 루트 노드 주소값을 스택에 집어 넣는다.
4) 1~3)의 과정을 반복해서 최종적으로 생성된 수식 트리는 스택으로 들어간 마지막 트리다.
[전위, 중위, 후위 순회]
수식 트리의 장점은 순회 방식에 따라 수식을 전위, 중위, 후위 표기법의 수식으로 다양하게 출력이 가능하다.
이 부분은 이전에 이진 트리 구현에서 만들었던 함수를 그대로 이용하여 순회를 시키면 수식 출력이 간편하게 된다.
참고로 중위 순회 부분은 괄호를 포함한 로직이 추가가 되어 있다.
[수식 트리의 계산]
이전의 이진트리에서도 했었던 이야기지만, 이진 트리는 재귀적인 구조를 띈다.
그렇기 때문에 계산에서도 재귀적인 구조는 그대로 적용이 된다.
그래서 연산 과정 역시 재귀적으로 해결해나가면 되는 부분이다.
왼쪽 연산자는 왼쪽 서브트리를 타고 들어가서 계속 계산하며 올라오면 된다.
오른쪽 연산자도 마찬가지로 오른쪽 서브트리를 타고 들어가서 계속 계산하며 올라오면 된다.
그러다보면 최종적으로 루트 노드까지 와서 마지막으로 계산하고 결과를 확인할 수 있다.
그리고 재귀의 탈출 조건으로는 왼쪽과 오른쪽 자식이 없는 경우, 다시 말해서 단말 노드일 때다.
이 때는 데이터를 반환하고 return하는 것으로 재귀의 탈출 조건을 세웠다.
나름대로 정리한다고 정리는 했지만 아직도 제대로 정리가 안된 느낌이다.
비선형 자료구조부터는 확실히 리스트나 스택, 큐와는 성격이 다른 부분이 커서 그렇다고 생각한다.
구현하면서 작성한 소스코드에 주석을 하나하나 달아놓았다.
나중에 복습하면서 다시 보면 금방 떠올릴 수 있게 최대한 상세하게 적어두었다.
