자료구조
Stack(3) - 사칙 연산 계산기
blackbearwow
2022. 7. 8. 13:57
스택을 사용하여 [0-9+-*/()] 로 구성된 사칙연산을 계산할 수 있다.
스택에서 사칙연산하기 위해 사용하는 표기법은 후위 표기법(Postfix Notation)이다.
우리가 보통 사용하는 수식은 중위 표기법(Infix Notation)인데, 이것을 계산하려면 다음 두 단계를 거쳐야 한다.
1. 중위 표기법을 후위 표기법으로 변환
2. 후위 표기법을 계산
1. 중위 표기법을 후위 표기법으로 변환 (다익스트라의 중위-후위 표기 변환 알고리즘)
①입력받은 중위 표기식에서 토큰을 읽는다.
②토큰이 피연산자이면 토큰을 결과에 출력한다.
③토큰이 연산자(괄호 포함)인 경우, 스택의 최상위 노드에 담겨있는 연산자가 토큰보다 우선 순위가 높은지를 검사한다. 검사 결과가 참이면 최상위 노드를 스택에서 꺼내 결과에 출력하며, 이 검사 작업을 반복해서 수행하되 그 결과가 거짓이거나 스택이 비게 되면 작업을 중단한다. 검사 작업이 끝난 후에는 토큰을 스택에 삽입한다. (이로 인해 스택에는 최상위 노드보다 우선순위가 높은 연산자는 존재하지 않게 됩니다.)
④토큰이 오른쪽 괄호 ')'이면 최상위 노드에 왼쪽 괄호 '('가 올 때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지는 않는다.
⑤중위 표기식에 더 읽을 것이 없다면 빠져나가고, 더 읽을 것이 있다면 ①부터 다시 반복한다.
2. 후위 표기법을 계산
// gcc -o Test_Calculator.exe Test_Calculator.c Calculator.c LinkedListStack.c; ./Test_Calculator.exe
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct tagNode
{
char* Data;
struct tagNode* NextNode;
} Node;
typedef struct tagLinkedListStack
{
Node* List;
Node* Top;
} LinkedListStack;
void LLS_CreateStack(LinkedListStack** Stack)
{
/* 스택을 자유저장소에 생성 */
(*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
(*Stack)->List = NULL;
(*Stack)->Top = NULL;
}
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; /* 다음 노드에 대한 포인터는 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
{
/* 최상위 노드를 찾아 NewNode를 연결한다(쌓는다). */
Node* OldTop = Stack->List;
while ( OldTop->NextNode != NULL )
{
OldTop = OldTop->NextNode;
}
OldTop->NextNode = NewNode;
}
/* 스택의 Top 필드에 새 노드의 주소를 등록한다. */
Stack->Top = NewNode;
}
Node* LLS_Pop(LinkedListStack* Stack)
{
/* LLS_Pop() 함수가 반환할 최상위 노드 */
Node* TopNode = Stack->Top;
if ( Stack->List == Stack->Top )
{
Stack->List = NULL;
Stack->Top = NULL;
}
else
{
/* 새로운 최상위 노드를 스택의 Top 필드에 등록한다. */
Node* CurrentTop = Stack->List;
while ( CurrentTop != NULL && CurrentTop->NextNode != Stack->Top )
{
CurrentTop = CurrentTop->NextNode;
}
Stack->Top = CurrentTop;
CurrentTop->NextNode = NULL;
}
return TopNode;
}
Node* LLS_Top(LinkedListStack* Stack)
{
return Stack->Top;
}
int LLS_GetSize(LinkedListStack* Stack)
{
int Count = 0;
Node* Current = Stack->List;
while ( Current != NULL )
{
Current = Current->NextNode;
Count++;
}
return Count;
}
int LLS_IsEmpty(LinkedListStack* Stack)
{
return (Stack->List == NULL);
}
typedef enum
{
LEFT_PARENTHESIS = '(', RIGHT_PARENTHESIS = ')',
PLUS = '+', MINUS = '-',
MULTIPLY = '*', DIVIDE = '/',
SPACE = ' ', OPERAND
} SYMBOL;
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;
}
int main( void )
{
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;
}