본문 바로가기
대학교 과제/자료구조 [ 2 - 1 ]

[자료구조 과제] - 12주차 수식트리 (후위표기식)

AGAPE1225 2020. 5. 29. 00:48
반응형

1. 과제안내문

이번 과제는 후위 표기식 형식으로 수식을 입력하여 수식트리를 만들고, 이 트리를 중위로 순회하면서 중위 표기식을 출력하고, 수식을 계산한 결과를 출력한다. 수식트리에서 노드는 연산자 또는 피연산자 노드로 구성되는데, 내부 노드는 연산자 노드이고, 외부 노드는 피연산자 노드가 된다. 피연산자 노드는 노드의 데이터는 피연산자가 되고 자식 노드는 없다. 연산자 노드는 노드의 데이터는 연산자가 되고, 피연산자들은 연산자 노드의 자식 노드로 연결된다. 이진연산자는 두 자식을 가지지만, 단일연산자는 왼쪽 자식은 없고 오른쪽 자식만 가진다. 수식트리를 만드는 방식은 후위 표기식을 계산하는 방식과 비슷하다. 피연산자는 피연산자 노드를 만들어 그 노드를 스택에 Push 한다. 연산자는 연산자 노드를 만들고, 자식 노드는 스택에서 Pop 하여 오른쪽 자식과 왼쪽 자식으로 연결한 후(단일연산자이면 왼쪽 자식은 없다) 그 노드를 스택에 Push 한다. 연산자는 C 언어에서 사용하는 산술연산자(+, -, *, /, %), 관계연산자(>, >=, ==, !=, <=, <), 논리연산자(!, &&, ||)로 구성된다. 피연산자는 정수로 제한한다. 마지막으로 대입연산자(=)는 수식트리를 중위로 순회하여 중위 표기식을 출력하고, 수식트리를 계산하여 수식의 값을 출력한다.

 사실 후위 표기법에 대한 계산은 스택을 혼자 공부했을 때 경험한 적이 있다. 피연산자들을 push하고 연산자가 나왔을 때, 그 값을 계산하여 다시 push하는 알고리즘을 사용했었다. 이번에는 tree로 계산되는 것이다. 알고리즘은 뒤에서 설명할 것이다. 다음은 실행 예시이다.

 

2. 결과시행 예시

? 1 // (A + B) * C

 

? 2

 

? +

 

? 3

 

? *

 

? =

Infix: ((1 + 2) * 3)

Result: 9

 

Once More(y/*) ? y

 

? 1 // A + B * C

 

? 2

 

? 3

 

? *

 

? +

 

? =

Infix: (1 + (2 * 3))

Result: 7

 

Once More(y/*) ? y

 

? 2000 // 윤년: year % 4 == 0 && year % 100 || year % 400 == 0

 

? 4

 

? %

 

? 0

 

? ==

 

? 2000

 

? 100

 

? %

 

? &&

 

? 2000

 

? 400

 

? %

 

? 0

 

? ==

 

? ||

 

? =

Infix: ((((2000 % 4) == 0) && (2000 % 100)) || ((2000 % 400) == 0))

Result: 1

 

Once More(y/*) n

 

Bye, ...

 조금 중요하게 생각한 부분은 바로 게산 순서에 따라 괄호를 출력해야 한다는 것이었다. 이 부분을 해결하는 과정도 조금 있다 설명할 것이다.

 

3. 코드구현

 

 우리 교수님의 과제는 내가 만들어야 하는 함수를 비워놓고 제시하여주신다. 다음은 처음으로 받은 코드들이다.

 

#include <stdio.h>
#include <stdlib.h>

#pragma warning (disable: 4996)

typedef struct nodet {							// 트리를 위한 노드
	int nData;
	struct nodet *lChild;
	struct nodet *rChild;
}	Nodet, *NodetPtr, Tree, *TreePtr;

typedef struct nodel {							// 스택을 위한 노드
	NodetPtr pData;
	struct nodel *link;
}	Nodel, *NodelPtr, Stack, *StackPtr;

enum { UnryOP, BnryOP, AsgnOP, Operand };		// 단일, 이진, 대입 연산자 그리고 피연산자

void main()
{
	void ExprTree();
	char sMore[10];
	do {
		ExprTree();
		printf("Once More(y/*) ? ");
		gets_s(sMore);
		putchar('\n');
	} while (sMore[0] == 'y');
	printf("Bye, ...\n");
}

void ExprTree()
{	// 이 함수는 수식을 후위 표기식 형식으로 입력받아 수식트리를 생성하고 
	// 수식트리를 중위로 순회하여 중위 표기식을 출력하고 수식의 값을 계산하여 출력한다.
	int GetToken(char sInput[], int &nToken, int &nOprnd);
	NodetPtr OperandNode(int nOprnd);
	NodetPtr OperatorNode(int nOprtr, TreePtr pTree1, TreePtr pTree2);
	void Push(StackPtr &pStack, TreePtr pTree);
	NodetPtr Pop(StackPtr &pStack);
	void InfixExpr(TreePtr pTree);
	int EvalExpr(TreePtr pTree, int &nResult);
	//
	// ???
	//
}

int GetToken(char sInput[], int &nToken, int &nOprnd)
{	// +,-,*,/,%,>,>=,==,!=,<=,<,!,&&,||,=,number
	int nCategory;
	switch (nToken = *(short *)sInput) {
	case 0x21:		// !
		nCategory = UnryOP;
		break;
	case 0x2B:		// +
	case 0x2D:		// -
	case 0x2A:		// *
	case 0x2F:		// /
	case 0x25:		// %
	case 0x3E:		// >
	case 0x3D3E:	// >=
	case 0x3D3D:	// ==
	case 0x3D21:	// !=
	case 0x3D3C:	// <=
	case 0x3C:		// <
	case 0x2626:	// &&
	case 0x7C7C:	// ||
		nCategory = BnryOP;
		break;
	case 0x3D:		// =
		nCategory = AsgnOP;
		break;
	default:
		nCategory = Operand;
		nOprnd = atoi(sInput);
	}
	return nCategory;
}

void InfixExpr(TreePtr pTree)
{	// 수식트리를 중위로 순회하여 중위 표기식을 출력한다.
}

int EvalExpr(TreePtr pTree, int &nResult)
{	// 수식트리에 대한 수식의 값을 계산하여 nResult에 저장하고 true/false를 반환한다.
	return true;
}

NodetPtr OperandNode(int nOprnd)
{	// 노드의 데이터로 피연산자 nOprnd를 가지는 피연산자 노드를 생성하여 반환한다.
	return NULL;
}

NodetPtr OperatorNode(int nOprtr, TreePtr pTree1, TreePtr pTree2)
{	// 데이터가 nOprtr, 왼쪽 자식이 pTree1, 오른쪽 자식이 pTree2인 연산자 노드를 생성하여 반환한다.
	return NULL;
}

void Push(StackPtr &pStack, TreePtr pTree)
{
}

NodetPtr Pop(StackPtr &pStack)
{
	return NULL;
}

 

 조금 복잡할 수 있겠지만, 주석에 따라 구현만 하면 된다. 여기서 눈에 띄이는 함수인 GetToken은 내가 입력받은 값이 단항인지 이항인지 피연산자인지를 구분하여 그에 따른 값을 반환해주는 함수이다. 이 부분은 이렇게만 알고있도록 하자.

 

- Push(), Pop()구현

 

 이번 Push(), Pop() 함수는 스택의 기본적인 메소드들이지만 조금 다른점이 있다면, 요소로 tree를 가진다는 것이다. 다음은 내가 구현한 Pop()과 Push() 이다.

 

void Push(StackPtr &pStack, TreePtr pTree)
{
	StackPtr pNew = new Stack;
	pNew->pData = pTree;
	if (pStack) 
		pNew->link = pStack;
	else
		pNew->link = NULL;
	pStack = pNew;
}

NodetPtr Pop(StackPtr &pStack)
{
	NodetPtr rTree = NULL;
	if (pStack) {
		StackPtr pDel = pStack;
		pStack = pDel->link;
		rTree = pDel->pData;
		delete pDel;
	}
	return rTree;
}

 

- operandNode(), OperatorNode() 구현

 

 이 두 함수들의 역할은 어떻게 보면 간단하다. 피연산자가 입력되었을 때 실행되는 OperandNode()함수는 양쪽 자식의  link가 NULL이고, 해당 피 연산자가 요소인 Tree를 만들면 되고 연산자가 입력되었을 때 실행되는 OperatorNode()는 양쪽 자식이 피연산자를 저장한 Tree이고, 연산자를 요소로 저장해주면 된다. 다음은 내가 작성한 함수들이다.

 

NodetPtr OperandNode(int nOprnd)
{	// 노드의 데이터로 피연산자 nOprnd를 가지는 피연산자 노드를 생성하여 반환한다.
	TreePtr pTree = new Tree;
	if (pTree) {
		pTree->nData = nOprnd;
		pTree->lChild = pTree->rChild = NULL;
	}
	return pTree;
}

NodetPtr OperatorNode(int nOprtr, TreePtr pTree1, TreePtr pTree2)
{	// 데이터가 nOprtr, 왼쪽 자식이 pTree1, 오른쪽 자식이 pTree2인 연산자 노드를 생성하여 반환한다.
	TreePtr pTree = new Tree;
	if (pTree) {
		pTree = new Tree;
		pTree->nData = nOprtr;
		pTree->lChild = pTree1;
		pTree->rChild = pTree2;
	}
	return pTree;
}

 

- InfixExpr() 함수

 

 이 함수는 수식트리를 중위로 순회하여 중위 표기짓을 출력하는 함수이다. 조금 조심해야할 것이 있다면 바로, 괄호를 출력해야 한다는 것과 순환함수를 사용해야 한다는것. 사실 순환함수가 필수라고는 하지 않으셨지만, 이젠 내가 더 편해졌다.(세뇌의 힘인지 아니면 정말 순환함수가 편한건지......) 각설하고 알고리즘을 설명하자면 연산자를 만났을 때, 여는 괄화와 왼쪽 Tree, 연산자 출력, 오른쪽 Tree, 닫는 괄호를 순서대로 출력하면 나름 간단하다. 다음 내가 작성한 함수의 코드이다.

 

void InfixExpr(TreePtr pTree)
{	// 수식트리를 중위로 순회하여 중위 표기식을 출력한다.
	if (pTree) {
		if (pTree->lChild || pTree->rChild) {
			printf("(");
			InfixExpr(pTree->lChild);
			printf(" %c ", pTree->nData);
			InfixExpr(pTree->rChild);
			printf(")");
		}
		else
			printf("%d", pTree->nData);	
	}
}

 

- EvalExpr() 함수

 

 이 함수의 알고리즘을 설명하자면, 왼쪽 Tree의 값과 오른쪽 Tree의 값을 해당 Tree에 저장되어있는 연산자에 따라 계산해 주면 된다. 세뇌의 힘인지 모르겠지만 나는 이 함수역시, 순환함수로 작성하였다. 순서를 굳이 명시하자면 후위 탐색이 될 것이다. 일단 왼쪽 Tree의 결과와 오른쪽 Tree의 결과를 받아 계산하기 때문이다. 계산은 연산자를 switch문으로 ㄱ분하여 case를 일일이 따져줬다. (분명 더욱 간단한 방법이 있겠지만 이것이 나의 최선이다......) 다음은 내가 작성한 코드이다.

 

int EvalExpr(TreePtr pTree, int &nResult)
{	// 수식트리에 대한 수식의 값을 계산하여 nResult에 저장하고 true/false를 반환한다.
	if (pTree) {
		if (pTree->lChild || pTree->rChild) {
			int lResult, rResult;
			EvalExpr(pTree->lChild, lResult);
			EvalExpr(pTree->rChild, rResult);
			switch (pTree->nData) {
			case '!':
				nResult = !rResult;
				break;
			case '+':
				nResult = lResult + rResult;
				break;
			case '-':
				nResult = lResult - rResult;
				break;
			case '*':
				nResult = lResult * rResult;
				break;
			case '/':
				nResult = lResult / rResult;
				break;
			case '%':
				nResult = lResult % rResult;
				break;
			case '>':
				nResult = lResult > rResult;
				break;
			case '>=':
				nResult = lResult >= rResult;
				break;
			case '!=':
				nResult = lResult != rResult;
				break;
			case '==':
				nResult = lResult == rResult;
				break;
			case '<=':
				nResult = lResult <= rResult;
				break;
			case '<':
				nResult = lResult < rResult;
				break;
			case '||':
				nResult = lResult || rResult;
				break;
			case '&&':
				nResult = lResult && rResult;
				break;
			}
		}
		else
			nResult = pTree->nData;
	}
	return true;
}

 

- ExprTree() 함수

 

 사실상 이 함수가 이 프로그램의 main() 함수라고 생각한다. 알고리즘은 의외로 간단하다. 입력받은 값을 GetToken()함수를 통해 어떤 값인지를 판단하고 그 값에 내가 제작한 알맞은 함수를 호출하여 처리해주면 되기 때문이다. 다음은 내가 작성한 ExprtTree() 함수이다.

 

void ExprTree()
{	// 이 함수는 수식을 후위 표기식 형식으로 입력받아 수식트리를 생성하고 
	// 수식트리를 중위로 순회하여 중위 표기식을 출력하고 수식의 값을 계산하여 출력한다.
	int GetToken(char sInput[], int &nToken, int &nOprnd);
	NodetPtr OperandNode(int nOprnd);
	NodetPtr OperatorNode(int nOprtr, TreePtr pTree1, TreePtr pTree2);
	void Push(StackPtr &pStack, TreePtr pTree);
	NodetPtr Pop(StackPtr &pStack);
	void InfixExpr(TreePtr pTree);
	int EvalExpr(TreePtr pTree, int &nResult);

	StackPtr stack = NULL;
	TreePtr pTree;
	bool endState = false;
	int nResult;

	while (1) {
		char input[10];
		printf("\n? ");
		scanf("%s", input);
		getchar();
		int nInt, nOpr;
		int token = GetToken(input, nOpr, nInt);

		switch (token) {
		case 0:
			pTree = OperatorNode(nOpr, NULL, Pop(stack));
			Push(stack, pTree);
			break;
		case 1:
		{
			TreePtr rTree = Pop(stack);
			TreePtr lTree = Pop(stack);
			pTree = OperatorNode(nOpr, lTree, rTree);
			Push(stack, pTree);
			break;
		}
		case 2:
			pTree = Pop(stack);
			endState = true;
			break;
		case 3:
			pTree = OperandNode(nInt);
			Push(stack, pTree);
			break;
		}
		if (endState)
			break;
	}
	printf(" Infix: ");
	InfixExpr(pTree);
	EvalExpr(pTree, nResult);
	printf("\nResult: %d\n\n", nResult);
}

 

- 전체 코드

 

다음은 이 과제의 전체 코드이다.

 

#include <stdio.h>
#include <stdlib.h>

#pragma warning (disable: 4996)

typedef struct nodet {							// 트리를 위한 노드
	int nData;
	struct nodet *lChild;
	struct nodet *rChild;
}	Nodet, *NodetPtr, Tree, *TreePtr;

typedef struct nodel {							// 스택을 위한 노드
	NodetPtr pData;
	struct nodel *link;
}	Nodel, *NodelPtr, Stack, *StackPtr;

enum { UnryOP, BnryOP, AsgnOP, Operand };		// 단일, 이진, 대입 연산자 그리고 피연산자

void main()
{
	void ExprTree();
	char sMore[10];
	do {
		ExprTree();
		printf("Once More(y/*) ? ");
		gets_s(sMore);
		putchar('\n');
	} while (sMore[0] == 'y');
	printf("Bye, ...\n");
}

void ExprTree()
{	// 이 함수는 수식을 후위 표기식 형식으로 입력받아 수식트리를 생성하고 
	// 수식트리를 중위로 순회하여 중위 표기식을 출력하고 수식의 값을 계산하여 출력한다.
	int GetToken(char sInput[], int &nToken, int &nOprnd);
	NodetPtr OperandNode(int nOprnd);
	NodetPtr OperatorNode(int nOprtr, TreePtr pTree1, TreePtr pTree2);
	void Push(StackPtr &pStack, TreePtr pTree);
	NodetPtr Pop(StackPtr &pStack);
	void InfixExpr(TreePtr pTree);
	int EvalExpr(TreePtr pTree, int &nResult);

	StackPtr stack = NULL;
	TreePtr pTree;
	bool endState = false;
	int nResult;

	while (1) {
		char input[10];
		printf("\n? ");
		scanf("%s", input);
		getchar();
		int nInt, nOpr;
		int token = GetToken(input, nOpr, nInt);

		switch (token) {
		case 0:
			pTree = OperatorNode(nOpr, NULL, Pop(stack));
			Push(stack, pTree);
			break;
		case 1:
		{
			TreePtr rTree = Pop(stack);
			TreePtr lTree = Pop(stack);
			pTree = OperatorNode(nOpr, lTree, rTree);
			Push(stack, pTree);
			break;
		}
		case 2:
			pTree = Pop(stack);
			endState = true;
			break;
		case 3:
			pTree = OperandNode(nInt);
			Push(stack, pTree);
			break;
		}
		if (endState)
			break;
	}
	printf(" Infix: ");
	InfixExpr(pTree);
	EvalExpr(pTree, nResult);
	printf("\nResult: %d\n\n", nResult);
}

int GetToken(char sInput[], int &nToken, int &nOprnd)
{	// +,-,*,/,%,>,>=,==,!=,<=,<,!,&&,||,=,number
	int nCategory;
	switch (nToken = *(short *)sInput) {
	case 0x21:		// !
		nCategory = UnryOP;
		break;
	case 0x2B:		// +
	case 0x2D:		// -
	case 0x2A:		// *
	case 0x2F:		// /
	case 0x25:		// %
	case 0x3E:		// >
	case 0x3D3E:	// >=
	case 0x3D3D:	// ==
	case 0x3D21:	// !=
	case 0x3D3C:	// <=
	case 0x3C:		// <
	case 0x2626:	// &&
	case 0x7C7C:	// ||
		nCategory = BnryOP;
		break;
	case 0x3D:		// =
		nCategory = AsgnOP;
		break;
	default:
		nCategory = Operand;
		nOprnd = atoi(sInput);
	}
	return nCategory;
}

void InfixExpr(TreePtr pTree)
{	// 수식트리를 중위로 순회하여 중위 표기식을 출력한다.
	if (pTree) {
		if (pTree->lChild || pTree->rChild) {
			printf("(");
			InfixExpr(pTree->lChild);
			printf(" %c ", pTree->nData);
			InfixExpr(pTree->rChild);
			printf(")");
		}
		else
			printf("%d", pTree->nData);	
	}
}

int EvalExpr(TreePtr pTree, int &nResult)
{	// 수식트리에 대한 수식의 값을 계산하여 nResult에 저장하고 true/false를 반환한다.
	if (pTree) {
		if (pTree->lChild || pTree->rChild) {
			int lResult, rResult;
			EvalExpr(pTree->lChild, lResult);
			EvalExpr(pTree->rChild, rResult);
			switch (pTree->nData) {
			case '!':
				nResult = !rResult;
				break;
			case '+':
				nResult = lResult + rResult;
				break;
			case '-':
				nResult = lResult - rResult;
				break;
			case '*':
				nResult = lResult * rResult;
				break;
			case '/':
				nResult = lResult / rResult;
				break;
			case '%':
				nResult = lResult % rResult;
				break;
			case '>':
				nResult = lResult > rResult;
				break;
			case '>=':
				nResult = lResult >= rResult;
				break;
			case '!=':
				nResult = lResult != rResult;
				break;
			case '==':
				nResult = lResult == rResult;
				break;
			case '<=':
				nResult = lResult <= rResult;
				break;
			case '<':
				nResult = lResult < rResult;
				break;
			case '||':
				nResult = lResult || rResult;
				break;
			case '&&':
				nResult = lResult && rResult;
				break;
			}
		}
		else
			nResult = pTree->nData;
	}
	return true;
}

NodetPtr OperandNode(int nOprnd)
{	// 노드의 데이터로 피연산자 nOprnd를 가지는 피연산자 노드를 생성하여 반환한다.
	TreePtr pTree = new Tree;
	if (pTree) {
		pTree->nData = nOprnd;
		pTree->lChild = pTree->rChild = NULL;
	}
	return pTree;
}

NodetPtr OperatorNode(int nOprtr, TreePtr pTree1, TreePtr pTree2)
{	// 데이터가 nOprtr, 왼쪽 자식이 pTree1, 오른쪽 자식이 pTree2인 연산자 노드를 생성하여 반환한다.
	TreePtr pTree = new Tree;
	if (pTree) {
		pTree = new Tree;
		pTree->nData = nOprtr;
		pTree->lChild = pTree1;
		pTree->rChild = pTree2;
	}
	return pTree;
}

void Push(StackPtr &pStack, TreePtr pTree)
{
	StackPtr pNew = new Stack;
	pNew->pData = pTree;
	if (pStack) 
		pNew->link = pStack;
	else
		pNew->link = NULL;
	pStack = pNew;
}

NodetPtr Pop(StackPtr &pStack)
{
	NodetPtr rTree = NULL;
	if (pStack) {
		StackPtr pDel = pStack;
		pStack = pDel->link;
		rTree = pDel->pData;
		delete pDel;
	}
	return rTree;
}

 

 

3. 결어

 

 Tree()라는 자료구조가, 어찌보면 복잡하고 어찌보면 단순하지만, 가장 중요한 것은 확실한 개념과 탐색의 학습인 것 같다. 탐색을 확실히 알았다면 이 과제가 그렇게 어렵지도 않았을 것이다.

 변명이겠지만 최근 블로그 업데이트가 매우 늦어지고 있다. 백준 알고리즘도 하나의 문제에 막히고 있고, Java는 풀었지만 올리지 못하고 있다. 게을러진 것 같다. 반성할 것이다 ㅠㅠ 

반응형

'대학교 과제 > 자료구조 [ 2 - 1 ]' 카테고리의 다른 글

[자료구조 과제] - 11주차 완전 이진 트리  (0) 2020.05.21
자료구조 10주차 과제 - 이중 원형 연결리스트  (0) 2020.05.12
자료구조 9주차 과제 - 원형 리스트  (0) 2020.05.02

'대학교 과제/자료구조 [ 2 - 1 ]' Related Articles

티스토리툴바