1. Stack의 응용
Stack은 활용도가 많은 편은 아닙니다. 하지만 Stack이라는 자료구조로 만들 수 있는것은 엄청나게 많습니다. 그 중 사칙 연산 계산기를 만들어볼까 합니다.
공학용 계산기같은 계산은 못합니다.
2. 수식표기법
사칙 연산 계산기를 만들기 전에 먼저 수식표기법에 대해 알아야 합니다. 수식 표기법에는 전위법, 중위법, 후위법 3가지로 나누어져있습니다.
전위법는 말 그대로 앞에서 부터 계산하는 방법이 아닙니다. 수식을 앞으로 뺀 표기법입니다.
중위법는 우리가 지금까지 많이 사용했던 괄호가 있는 방식입니다. 계산 순서가 직관적으로 명확하지 않습니다.
후위법도 또한 뒤에서 부터 계산하는 방법이 아닌, 수식을 뒤로 뺀 표기법입니다.
전위법과 후위법은 계산순서에 따라서 수식을 배치했기 때문에 괄호없이도 계산 순서가 직관적입니다. 컴퓨터 프로그래밍은 복잡한 순서규칙이 있는 것 보다는 단순한 규칙을 선호하기 때문에, 전위법과 후위법으로 계산하는 것이 편합니다.
따라서 이번 사칙 연산 계산기는 후위법으로 구현해볼까 합니다.
후위법
중위 표기법으로 표기된
3+2+4*5+3/1
를 후위 표기법으로 바꿔봅니다. 우선 연산자 우선순위에 맞게 괄호를 쳐줍니다.
((3+2)+(4*5))+(3/1)
이 괄호 안에 있는 연산자들을 뒤로 빼줍니다.
(((32)+(45)*)+(31)/)+
괄호를 모두 없애줍니다.
32+45*+31/+
해당 식이 후위 표기법으로 나타낸 식입니다.
후위법을 계산하는 방법은 연산자를 만나면 앞에있는 피연산자 2개를 연산하는 것입니다.
위에식에서는
3 2 +만 따로 계산을 해주면
5 4 5 * + 3 1 / +
만 남게됩니다. 여기서 앞에 45이기 때문에, 45를 해줍니다.
5 20 + 3 1 / +
여기서 5 + 20을 해줍니다.
25 3 1 / +
3/1 해줍니다.
25 3 +
따라서 결과는 28입니다.
근데 Stack을 어디서 사용하는지를 모를 수도 있습니다. 중위법에서 후위법으로 바뀔 때 연산자를 담는 용도로 사용됩니다. 다음의 순서대로 진행됩니다.
-
숫자가 나오면 그대로 출력한다.
-
(나오면 스택에 push한다. -
*/나오면 스택에 push한다. -
+-연산이 나오면 여는 괄호(, 여는 괄호가 없다면 스택의 끝까지 출력하고 그 연산자를 스택에 push한다. -
닫는 괄호
)가 나오면 여는 괄호(가 나올때까지 pop하여 출력한다.
3. 사칙 연산 계산기 구현
헤더파일
사칙 연산 계산기를 구현할 때 StackLinkedList를 사용하겠습니다. 헤더파일을 보이기 전에 StackLinkedList의 헤더파일과 소스파일의 코드를 먼저 보겠습니다.
LinkeListStack.h
#ifndef LINKEDLIST_STACK_H
#define LINKEDLIST_STACK_H
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct tagNode
{
char* Data;
struct tagNode* NextNode;
struct tagNode* PrevNode;
} Node;
typedef struct tagLinkedListStack
{
int Count;
Node* List;
Node* Top;
} LinkedListStack;
void LLS_CreateStack(LinkedListStack** Stack);
void LLS_DestroyStack(LinkedListStack* Stack);
Node* LLS_CreateNode(char* Data);
void LLS_DestroyNode(Node* _Node);
void LLS_Push(LinkedListStack* Stack, Node* NewNode);
Node* LLS_Pop(LinkedListStack* Stack);
Node* LLS_Top(LinkedListStack* Stack);
int LLS_GetSize(LinkedListStack* Stack);
int LLS_IsEmpty(LinkedListStack* Stack);
#endif
LinkedListStack.c
#define _CRT_SECURE_NO_WARNINGS
#include "LinkedListStack.h"
void LLS_CreateStack(LinkedListStack** Stack)
{
(*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
(*Stack)->List = NULL;
(*Stack)->Top = NULL;
(*Stack)->Count = 0;
}
void LLS_DestroyStack(LinkedListStack* Stack)
{
while (!LLS_IsEmpty(Stack))
{
Node* Popped = LLS_Pop(Stack);
LLS_DestroyNode(Popped);
}
free(Stack);
}
Node* LLS_CreateNode(char* NewData)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = (char*)malloc(strlen(NewData) + 1);
strcpy(NewNode->Data, NewData);
NewNode->NextNode = NULL;
NewNode->PrevNode = NULL;
return NewNode;
}
void LLS_DestroyNode(Node* _Node)
{
free(_Node->Data);
free(_Node);
}
void LLS_Push(LinkedListStack* Stack, Node* NewNode)
{
if (Stack->List == NULL)
{
Stack->List = NewNode;
}
else
{
Stack->Top->NextNode = NewNode;
NewNode->PrevNode = Stack->Top;
}
Stack->Top = NewNode;
Stack->Count++;
}
Node* LLS_Pop(LinkedListStack* Stack)
{
Node* TopNode = Stack->Top;
if (Stack->List == Stack->Top)
{
Stack->List = NULL;
Stack->Top = NULL;
}
else
{
Stack->Top = Stack->Top->PrevNode;
Stack->Top->NextNode->PrevNode = NULL;
Stack->Top->NextNode = NULL;
}
Stack->Count--;
return TopNode;
}
Node* LLS_Top(LinkedListStack* Stack)
{
return Stack->Top;
}
int LLS_GetSize(LinkedListStack* Stack)
{
return Stack->Count;
}
int LLS_IsEmpty(LinkedListStack* Stack)
{
return (Stack->List == NULL);
}
그럼 Calculator 헤더파일을 보겠습니다. 참고로 Calculator는 계산기 함수를 구현해놓은 파일명입니다.
Calculator.h
#ifndef CALCULATOR_H
#define CALCULATOR_H
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include "LinkedListStack.h"
typedef enum { //연산자들을 열겨형을 이용해 정수로 치환합니다. (switch문 사용 가능)
LEFT_PARENTHESIS = '(', RIGHT_PARENTHESIS = ')',
PLUS = '+', MINUS = '-', MULTIPLY = '*', DIVIDE = '/',
SPACE = ' ', OPERAND
}SYMBOL;
int IsNumber(char Ciper); -> 숫자인지 알려주는 함수
unsigned int GetNextToken(char* Expression, char* Token, int* TYPE); -> 중위법에 있는 숫자 연산자 괄호등을 토큰으로 묶어주는 함수
int IsPrior(char Operator1, char Operator2); -> 연산자의 우선순위를 알려주는 함수
void GetPostfix(char* InfixExpression, char* PostfixExpression); -> 중위법의 연산법을 후위법으로 바꿔주는 함수
double Calculate(char* PostfixExpression); -> 후위법으로 계산해주는 함수
#endif헤더파일에서 함수의 이름과 변수의 이름으로 함수의 역할들을 파악하는 것은 어려운 일이 아님을 알 수 있습니다. 여기서 중요한 함수는 GetPostfix함수와 Calculate함수입니다. 소스파일을 보면서, 좀 더 자세히 알아보겠습니다.
소스파일
Calculator.c
#include "Calculator.h"
char NUMBER[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.' };
int IsNumber(char Cipher) {
int i = 0;
int ArrayLength = sizeof(NUMBER);
for (i = 0; i < ArrayLength; i++) {
if (Cipher == NUMBER[i]) {
return 1;
}
}
return 0;
}
unsigned int GetNextToken(char* Expression, char* Token, int* TYPE) {
unsigned int i = 0;
for (i = 0; 0 != Expression[i]; i++) {
Token[i] = Expression[i];
if (IsNumber(Expression[i]) == 1) {
*TYPE = OPERAND;
if (IsNumber(Expression[i + 1]) != 1) {
break;
}
}
else {
*TYPE = Expression[i];
break;
}
}
Token[++i] = '\0';
return i;
}
int GetPriority(char Operator, int InStack) {
int Priority = -1;
switch (Operator) {
case LEFT_PARENTHESIS:
if (InStack)
Priority = 3;
else
Priority = 0;
break;
case MULTIPLY:
case DIVIDE:
Priority = 1;
break;
case PLUS:
case MINUS:
Priority = 2;
break;
}
return Priority;
}
int IsPrior(char OperatorInStack, char OperatorInToken) {
return (GetPriority(OperatorInStack, 1) > GetPriority(OperatorInToken, 0));
}
void GetPostfix(char* InfixExpression, char* PostfixExpression) {
LinkedListStack* Stack;
char Token[32];
int Type = -1;
unsigned int Position = 0;
unsigned int Length = strlen(InfixExpression);
LLS_CreateStack(&Stack);
while (Position < Length) {
Position += GetNextToken(&InfixExpression[Position], Token, &Type);
if (Type == OPERAND) {
strcat(PostfixExpression, Token);
strcat(PostfixExpression, " ");
}
else if (Type == RIGHT_PARENTHESIS) {
while (!LLS_IsEmpty(Stack)) {
Node* Popped = LLS_Pop(Stack);
if (Popped->Data[0] == LEFT_PARENTHESIS) {
LLS_DestroyNode(Popped);
break;
}
else {
strcat(PostfixExpression, Popped->Data);
LLS_DestroyNode(Popped);
}
}
}
else {
while (!LLS_IsEmpty(Stack) && !IsPrior(LLS_Top(Stack)->Data[0], Token[0])) {
Node* Popped = LLS_Pop(Stack);
if (Popped->Data[0] != LEFT_PARENTHESIS)
strcat(PostfixExpression, Popped->Data);
LLS_DestroyNode(Popped);
}
LLS_Push(Stack, LLS_CreateNode(Token));
}
}
while (!LLS_IsEmpty(Stack)) {
Node* Popped = LLS_Pop(Stack);
if (Popped->Data[0] != LEFT_PARENTHESIS)
strcat(PostfixExpression, Popped->Data);
LLS_DestroyNode(Popped);
}
LLS_DestroyStack(Stack);
}
double Calculate(char* PostfixExpression) {
LinkedListStack* Stack;
Node* ResultNode;
double Result;
char Token[32];
int Type = -1;
unsigned int Read = 0;
unsigned int Length = strlen(PostfixExpression);
LLS_CreateStack(&Stack);
while (Read < Length) {
Read += GetNextToken(&PostfixExpression[Read], Token, &Type);
if (Type == SPACE)
continue;
if (Type == OPERAND) {
Node* NewNode = LLS_CreateNode(Token);
LLS_Push(Stack, NewNode);
}
else {
char ResultString[32];
double Operator1, Operator2, TempResult;
Node* OperatorNode;
OperatorNode = LLS_Pop(Stack);
Operator2 = atof(OperatorNode->Data);
LLS_DestroyNode(OperatorNode);
OperatorNode = LLS_Pop(Stack);
Operator1 = atof(OperatorNode->Data);
LLS_DestroyNode(OperatorNode);
switch (Type) {
case PLUS: TempResult = Operator1 + Operator2; break;
case MINUS: TempResult = Operator1 - Operator2; break;
case MULTIPLY: TempResult = Operator1 * Operator2; break;
case DIVIDE: TempResult = Operator1 / Operator2; break;
}
_gcvt(TempResult, 10, ResultString);
LLS_Push(Stack, LLS_CreateNode(ResultString));
}
}
ResultNode = LLS_Pop(Stack);
Result = atof(ResultNode->Data);
LLS_DestroyNode(ResultNode);
LLS_DestroyStack(Stack);
return Result;
}순서대로 함수를 보겠습니다. 먼저 IsNumber함수입니다.
char NUMBER[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.' };
int IsNumber(char Cipher) {
int i = 0;
int ArrayLength = sizeof(NUMBER);
for (i = 0; i < ArrayLength; i++) {
if (Cipher == NUMBER[i]) {
return 1;
}
}
return 0;
}먼저 NUMBER배열에는 모든 한자릿수 숫자가 저장되어있습니다. 거기에 .도 있는데, 소수도 포함한 계산이라 .도 포함시키는 모습입니다. 먼저 NUMBER배열의 요소하나하나와 비교하여 같은게 있으면 1, 없으면 0을 반환합니다.
다음은 GetNextToken함수입니다.
unsigned int GetNextToken(char* Expression, char* Token, int* TYPE) {
unsigned int i = 0;
for (i = 0; 0 != Expression[i]; i++) {
Token[i] = Expression[i];
if (IsNumber(Expression[i]) == 1) {
*TYPE = OPERAND;
if (IsNumber(Expression[i + 1]) != 1) {
break;
}
}
else {
*TYPE = Expression[i];
break;
}
}
Token[++i] = '\0';
return i;
}GetNextToken함수에서는 숫자면 숫자가 아닌 수가 나올 때까지, 숫자가 아니면 바로 Token에 넣어주고 있습니다. 그리고 /0을 끝에 넣어주고 i를 반환하는 모습입니다.
다음은 GetPriority함수와 IsPrior함수를 보겠습니다.
int GetPriority(char Operator, int InStack) {
int Priority = -1;
switch (Operator) {
case LEFT_PARENTHESIS:
if (InStack)
Priority = 3;
else
Priority = 0;
break;
case MULTIPLY:
case DIVIDE:
Priority = 1;
break;
case PLUS:
case MINUS:
Priority = 2;
break;
}
return Priority;
}
int IsPrior(char OperatorInStack, char OperatorInToken) {
return (GetPriority(OperatorInStack, 1) > GetPriority(OperatorInToken, 0));
}GetPriority함수에서는 연산자마다 Priority변수에 값을 넣어주는 모습입니다. 계산우선도가 높은 연산자일수록 더 큰 값을 넣어주고 있습니다.
IsPrior함수에서는 반환된 값을 비교해서 우선순위를 반환하는 모습입니다. 만약 앞의 연산자가 더 크면 1, 크지 않으면 0을 반환합니다.
다음 GetPostfix함수입니다.
void GetPostfix(char* InfixExpression, char* PostfixExpression) {
LinkedListStack* Stack;
char Token[32]; //토큰
int Type = -1;
unsigned int Position = 0;
unsigned int Length = strlen(InfixExpression);
LLS_CreateStack(&Stack); // 스택 생성
while (Position < Length) {
Position += GetNextToken(&InfixExpression[Position], Token, &Type); // 토큰에 숫자나 연산자넣기
if (Type == OPERAND) { //TYPE이 숫자일때
strcat(PostfixExpression, Token); // PostfixExpression에 토큰에 저장된 문자열 복사하기
strcat(PostfixExpression, " "); // 공백문자 넣어주기(구분하기 위해서 넣어주는 모습)
}
else if (Type == RIGHT_PARENTHESIS) { //TYPE이 오른쪽 괄호 일 때
while (!LLS_IsEmpty(Stack)) {
Node* Popped = LLS_Pop(Stack); // Stack에 저장된 연산자를 뽑아서
if (Popped->Data[0] == LEFT_PARENTHESIS) {
LLS_DestroyNode(Popped); // 뽑은 노드 삭제
break;
}
else {
strcat(PostfixExpression, Popped->Data); // PostfixExpression에 복사합니다.
LLS_DestroyNode(Popped);
}
}
}
else {
while (!LLS_IsEmpty(Stack) && !IsPrior(LLS_Top(Stack)->Data[0], Token[0])) {
//스택이 비거나, Token의 연산자의 우선순위가 Stack보다 높기 전까지 반복
Node* Popped = LLS_Pop(Stack); //Stack에서 연산자 뽑기
if (Popped->Data[0] != LEFT_PARENTHESIS)
strcat(PostfixExpression, Popped->Data); //PostfixExpression에 덧붙이기
LLS_DestroyNode(Popped); // 노드 삭제
}
LLS_Push(Stack, LLS_CreateNode(Token));
}
}
while (!LLS_IsEmpty(Stack)) { // 마지막으로 Stack에 남아있는 연산자들 다 PostfixExpression에 옮기기
Node* Popped = LLS_Pop(Stack);
if (Popped->Data[0] != LEFT_PARENTHESIS)
strcat(PostfixExpression, Popped->Data);
LLS_DestroyNode(Popped);
}
LLS_DestroyStack(Stack);
}조금 복잡해 보이지만 아주 간단하고, 효율적으로 중위법에서 후위법으로 바꾸고 있습니다.
이제 후위법으로 바꾼 연산을 계산해주는 Calculate함수를 보겠습니다.
double Calculate(char* PostfixExpression) {
LinkedListStack* Stack; //스택 생성
Node* ResultNode; //연산결과 노드 생성
double Result; //결과를 저장할 변수
char Token[32]; //토큰
int Type = -1; //TYPE저장 변수
unsigned int Read = 0; //어디까지 읽었는지 알려주는 변수
unsigned int Length = strlen(PostfixExpression); // PostfixExpression의 길이
LLS_CreateStack(&Stack); //스택 초기화
while (Read < Length) { //끝까지 읽을 때까지
Read += GetNextToken(&PostfixExpression[Read], Token, &Type);
if (Type == SPACE) //공백문자 건너띄기
continue;
if (Type == OPERAND) {// 숫자 Stack에 쌓기
Node* NewNode = LLS_CreateNode(Token);
LLS_Push(Stack, NewNode);
}
else { //연산자를 만나면 연산을 진행
char ResultString[32];
double Operator1, Operator2, TempResult;
Node* OperatorNode;
OperatorNode = LLS_Pop(Stack); //Stack에서 숫자를 Pop하기
Operator2 = atof(OperatorNode->Data);// 문자를 숫자로 바꿔주는 함수
LLS_DestroyNode(OperatorNode);
OperatorNode = LLS_Pop(Stack);
Operator1 = atof(OperatorNode->Data);
LLS_DestroyNode(OperatorNode);
switch (Type) { // 연산 진행
case PLUS: TempResult = Operator1 + Operator2; break;
case MINUS: TempResult = Operator1 - Operator2; break;
case MULTIPLY: TempResult = Operator1 * Operator2; break;
case DIVIDE: TempResult = Operator1 / Operator2; break;
}
_gcvt(TempResult, 10, ResultString); // 숫자를 문자로 바꿔주는 함수
LLS_Push(Stack, LLS_CreateNode(ResultString)); /계산결과 다시 Stack에 쌓기
}
}
ResultNode = LLS_Pop(Stack); //마지막 결과 Pop
Result = atof(ResultNode->Data); //숫자로 바꾸기
LLS_DestroyNode(ResultNode);
LLS_DestroyStack(Stack);
return Result; // 결과 반환
}계산할때도 Stack을 사용하는 모습입니다. GetPostfix함수와 다른점은 Calculate함수는 Stack에 숫자를 Push합니다. 함수를 보았을 때, 어려울 순 있으나 그림을 그려가면서, 차근차근 해석해나가면 점점 눈에 들어옵니다.
실행예시
적절한 Main함수를 구현하여, 계산을 진행해보겠습니다.
먼저 100 * 2 + 7을 먼저 입력하고, (117.32 + 83) * 49를 입력해보겠습니다.
결과 예상
1002+7 = 207
(117.32+83)49 = 9,815.68
CalCulatorMain.c
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include "Calculator.h"
int main() {
char InfixExpression[100];
char PostfixExpression[100];
double Result = 0.0;
memset(InfixExpression, 0, sizeof(InfixExpression));
memset(PostfixExpression, 0, sizeof(PostfixExpression));
printf("Enter Infix Expression:");
scanf("%s", InfixExpression);
GetPostfix(InfixExpression, PostfixExpression);
printf("Infix: %s\nPostfix: %s\n", InfixExpression, PostfixExpression);
Result = Calculate(PostfixExpression);
printf("Calculation Result : %f\n", Result);
return 0;
}결과
Enter Infix Expression:100*2+7
Infix: 100*2+7
Postfix: 100 2 *7 +
Calculation Result : 207.000000Enter Infix Expression:(117.32+83)*49
Infix: (117.32+83)*49
Postfix: 117.32 83 +49 *
Calculation Result : 9815.680000결과 예상과 결과가 같은 걸 보면 구현이 잘된 것같습니다.
게임개발공부블로그