본문 바로가기
자료구조

[자료구조] 스택 - 04 . 사칙 연산 계산기

파울로 디발자 2023. 1. 25. 23:12

[사칙 연산 계산기]

[사칙연산계산기]

=>사칙연산만으로 이루어진 식을 분석해서 풀어보려 한다.

ex)  1+3.334 / (4.28*(110-2279))

 

=>해당 문제를 사람이 본다면 , 우선순위가 눈에 들어오겠지만 컴퓨터는 아니다! 

: 컴퓨터가 사용 할 도구 (알고리즘)을 제공해야 한다.

 

=>알고리즘을 위한 과정은 이렇다

  1. 수식을 프로그램이 풀기 적당한 형식 (후위 표기법)으로 변환한다 .
  2. 변환된 수식을 프로그램이 계산한다 .

[수식의 표기법]

[전위 표기법  (Prefix Notation) ]

=>연산자가 피연산자 앞에 위치한다 . 폴리쉬 표기법이라고도 한다.

   ex) 3+4 => +34

 

[중위 표기법  (Infix Notation) ]

=>흔히 사용하는 표기법 .연산자가 피연산자 가운데에 위치한다 .

   ex) 3+4

 

[전위 표기법  (Postfix Notation) ]

=>연산자가 피연산자 뒤에 위치한다 . 역폴리쉬 표기법이라고도 한다.

   ex) 3+4 => 34 +

 

[후위 표기식 계산 알고리즘]

[ 계산 규칙 ]

=>후위 표기식을 계산하는 알고리즘은 두가지 규칙으로 이루어져 있다 .

  1. 식의 왼쪽부터 요소를 읽어내면서 피연산자는 스택에 담는다 .
  2. 연산자를 만나면 스택에서 피연산자 두개를 꺼내 연산하고 , 해당 연산 결과를 스택에 삽입한다 .

[ 예시 ]

=>1 3 2 * - 를 계산한다 . (중위 표기법 " 1 - 3 * 2 ")

  1. 연산자가 안보이니 1 , 3 , 2가 차례로 스택에 쌓인다 .
  2. 연산자 * 를 만나 스택에서 3,2 를 꺼내 * 연산한 결과 6을  스택에 쌓는다 (1 - 6이 쌓여있음)
  3. 연산자 - 를 만나 스택에서 1,6을 꺼내 - 연산한 결과 -5를 스택에 쌓는다 .
  4. 식을 모두 읽었느니 최종값을 스택에서 꺼낸다 .

[ 순서도 ]

[ 알고리즘 ]

=>주요 알고리즘은 이렇다 .
여기서 토큰은 최소단위의 기호 또는 단어를 말한다 .

double Calculate (char* PostfixExpression)
{
    ... // 스택 생성
    while(PostfixExpression을 끝까지 다 읽을때까지)
    {
    //후위 표기식에서 토큰을 읽어내고 , 읽은 토큰 크기를 Read에 누적한다 .
    Read+=GetNextToken(&PostfixExpression[Position],Token,&Type);
        
        if(Type==OPERAND)	//토큰이 피연산자라면
        {
        	//스택에 삽입
        	LLS_Push(&Stack,LLS_CreateNode(Token));
        }
        else				//토큰이 연산자라면
        {
            Operator1 = LLS_Pop(&Stack);
            Operator2 = LLS_Pop(&Stack);
            
            switch(Type)	//연산자의 종류에 따라 계산한다.
            {
            	case PLUS: TempResult = Operator1 + Operator2;break;
                case MINUS: TempResult = Operator1 - Operator2;break;
                case MULTIPLE: TempResult = Operator1 * Operator2;break;
                case DIVIDE: TempResult = Operator1 / Operator2;break;        
            }
            //계산 결과를 Stack에 쌓는다 .
            LLS_Push(&Stack,LLS_CreateNode(TempResult));
        }
    }
    //스택에 마지막 남아있는 결과값을 Result에 저장
    Result=LLS_Pop(&Stack);
    ... // 스택 소멸
    
    return Result;
}

[중위 표기식 => 후위 표기식 변환 알고리즘]

[ 계산 규칙 ]

=>중위 표기식을 후위 표기식으로 변환하는 알고리즘은 다음의 규칙으로 이루어져 있다 .

  1. 입력받은 중위표기식에서 토큰을 읽는다 .
  2. 토큰이 피연산자라면 토큰을 결과에 출력한다 .
  3. 토큰이 연산자(괄호 포함)라면 , 스택의 최상위 노드에 담겨있는 연산자가 토큰보다 우선순위가 높은지 검사한다.
  4. 스택의 최상위 노드에 담긴 연산자가 더 높다면 , 최상위 노드를 스택에서 꺼내 결과에 출력한다 .
  5. 해당 작업을 반복한다 .
  6. 스택의 최상위 노드에 담긴 연산자보다 토큰 연산자의 우선순위가 높거나 스택이 비었다면 , 작업을 중단하고 토큰을 스택에 삽입한다 . (스택에는 최상위 노드보다 우선순위가 높은 연산자는 존재하지 않는다)
  7. 토큰이 오른쪽 괄호 " ) " 라면 최상위 노드에 왼쪽 괄호가 올 때 까지 스택에 제거 연산을 수행 , 제거한 노드에 담긴 연산자를 출력한다 . 왼쪽 괄호를 만나면 제거만 하고 출력은 하지 않는다 .
  8. 중위 표기식에서 읽을 것이 없다면 빠져나가고 , 읽을 것이 있다면 1부터 반복한다 .

[ 예시 ]

=> (117.32 +83) * 49

  1. 토큰이 " ( " 일떄는 출력 :   스택 : (  
  2. 토큰이 " 117.32 " 일떄는 출력 : 117.32   스택 : (
  3. 토큰이 " + " 일떄는 출력 : 117.32   스택 : ( +
  4. 토큰이 " 83 " 일떄는 출력 : 117.32 83   스택 : ( +
  5. 토큰이 " ) " 일떄는 출력 : 117.32 83 +  스택 :
  6. 토큰이 " * " 일떄는 출력 : 117.32 83 +  스택 : *
  7. 토큰이 " 49 " 일떄는 출력 : 117.32 83 + 49 스택 : *
  8. 식 모두 읽었음 . 스택 연산자 모두 제거후 출력 => 117.32 83 + 49 *

[ 알고리즘 ]

=>주요 알고리즘은 이렇다 .

void GetPostfix(char* InfixExpression , char* PostfixExpression )
{
	LinkedList* Stack;
    
    char Token[32];
    int Type = -1 ;
    unsigned int Position = 0 ;
    unsigned int Length = strlen (InfixExpression);
    
    LLS_CreateStack(&Stack);
    
    while(Position < Length)
    {
    	Positioin += GetNextToken(& InfixExpression[Position] , Token , &Type);
        
        if(Type == OPERAN)		//토큰이 피연산자라면
        {
        	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(Token[0] , LLS_Top(Stack) -> Data[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);
        }
    }
	
    //중위표기식을 다 읽었으니 Stack에 남겨져 있는 모든 연산자를 후위 표기식에 출력한다
    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);
}

[후위 표기식 계산기 예제]

[ Calculator.h ]

#ifndef Cal
#define Cal
#define _CRT_SECURE_NO_WARNINGS

#include "LLS.h"

typedef enum 
{
	LEFT_PARENTHESIS = '(', RIGHT_PARENTHESIS=')',
	PLUS='+',MINUS='-',
	MULTIPLY='*',DIVIDE='/',
	SPACE=' ',OPERAND,
}SYMBOL;

//숫자인지 확인
bool IsNumber(char Ciper);
//토큰단위로 데이터를 받는다
unsigned int GetNextToken(char* Expression, char* Token, int* TYPE);
//우선순위를 받는다
int GetPriority(char Operator, int InStack);
//우선순위를 비교한다
bool IsPrior(char OperatorInStack, char OperatorInToken);
//중위 표기식을 후위 표기식으로 변경
void GetPostfix(char* InfixExpression, char* PostfixExpression);
//후위 표기식을 계산
double Calculate(char* PostfixExpression);


#endif // !Cal

[ Calculator.cpp ]

#include "Calculator.h"
#define _CRT_SECURE_NO_WARNINGS

char Number[] = {'0','1','2','3','4','5','6','7','8','9','.'};

//숫자인지 확인
bool IsNumber(char Ciper)
{
	int ArrayLength = sizeof(Number);

	for (int i = 0; i < ArrayLength; i++)
	{
		//숫자라면
		if (Ciper == Number[i])
			return true;
	}
	//아니라면
	return false;

}
//토큰단위로 데이터를 받는다
unsigned int GetNextToken(char* Expression, char* Token, int* TYPE)
{
	unsigned int i = 0;
	//표현식이 끝나기 전까지 일단 반복
	for (i = 0; Expression[i] != 0; i++)
	{
		Token[i] = Expression[i];

		//해당 계산식이 숫자라면
		if (IsNumber(Expression[i]))
		{
			*TYPE = OPERAND;
			//다음에 연산자가 나온다면 중단
			if (IsNumber(Expression[i + 1])==false)
				break;
		}
		else
		{
			*TYPE = Expression[i];
			break;

		}
	}
	//구분을 위해 NULL문자를 다음 토큰에 넣어준다
	Token[++i] = '\0';
	return i;
}
//우선순위를 받는다
int GetPriority(char Operator, int InStack)
{
	int Priority = -1;

	switch (Operator)
	{
	case LEFT_PARENTHESIS:
		Priority = InStack ? 3 : 0; break;
	case MULTIPLY:case DIVIDE:
		Priority = 1; break;
	case PLUS:case MINUS:
		Priority = 2; break;
	}
	return Priority;
}

//스택의 연산자가 토큰의 연산자보다 우선순위가 높은지 비교한다
bool IsPrior(char OperatorInStack, char OperatorInToken)
{
	return GetPriority(OperatorInStack,true) > GetPriority(OperatorInToken,false);
}

//중위 표기식을 후위 표기식으로 변경
void GetPostfix(char* InfixExpression, char* PostfixExpression)
{
	char Token[32];
	int Type = -1;
	unsigned int TokenPosition = 0;
	unsigned int InfixLength = strlen(InfixExpression);

	//스택을 생성
	Stack* _Stack;
	LLS_CreateStack(&_Stack);

	//중위 표기식을 다 읽을때까지
	while (TokenPosition < InfixLength)
	{
		//토큰 단위로 읽어온다 .
		TokenPosition += GetNextToken(&InfixExpression[TokenPosition], 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_TopNode(_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));
		}
	}

	//표기식을 다 읽었다면 스택이 빌때까지 Pop
	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)
{
	Stack* _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);

			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;
}

[Test.cpp]

#include "Calculator.h"
#define _CRT_SECURE_NO_WARNINGS
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\n Postfix:%s\n", InfixExpression, PostfixExpression);
	
	Result = Calculate(PostfixExpression);

	printf("Calculation Result : %f\n", Result);
	return 0;

}

'자료구조' 카테고리의 다른 글

[자료구조] 큐 - 02 . 순환큐  (0) 2023.01.31
[자료구조] 큐 - 01 . 큐  (0) 2023.01.30
[자료구조] 스택 - 03 . 링크드 리스트로 구현하는 스택  (0) 2023.01.24
[자료구조] 스택 - 02 . 배열로 구현하는 스택  (0) 2023.01.24
[자료구조] 스택 - 01 . 스택의 개념  (0) 2023.01.23

'자료구조' Related Articles

티스토리툴바