[자료구조] ch 2. 스택(2) - 사칙 연산 계산기

2.4 스택의 응용 : 사칙 연산 계산기 

 

- 수식 분석기 기반의 사칙 연산 계산기 

- 원본 수식을 컴퓨터가 풀기 쉬운 형식으로 변환 후 , 이렇게 변환된 수식을 계산

 

2.4.1 수식의 중위 표기법과 후위 표기법 

 

후위 표기법(Postfic Notation)

 - 연산자가 피연산자 뒤에 위치 

 - 1 2 33 /+9 13 * -

 

전위 표기법(Infix Notation)

 - 연산자가 피연산자 가운데에 위치 

 - 1+2/33-9*13

 

2.4.2 후위 표기식을 계산하는 알고리즘 

 

1) 식의 왼쪽부터 요소를 읽어내면서 그 요소가 피연산자라면 스택에 삽입 

2) 연산자가 나타나면 스택에서 피연산자 2개를 꺼내 연산을 실행하고 그 연산 결과를 다시 스택에 삽입 

 

 - 곱셈을 수행하는 *이므로 스택에서 두 번의 제거 연산을 수행하여 피연산자 2와 3을 꺼낸 후 '3*2'의 계산 결과인 6을 스택에 삽입 

- 스택에 1과 6이 저장됨

 - '-'연산자를 만났을 때 두 번의 제거 연산을 실행해서 피연산자 2개를 꺼내 계산 수행 

 - 6과 1을 스택에서 꺼낸 후 '1-6'의 계산 결과인 -5를 스택에 저장 

- 스택에는 식의 최종 계산 결과만 남음 

- 이 값을 스택에서 꺼내면 계산 결과를 얻을 수 있음

 

후위 표기식 계산 함수 Calculate()

double Calculate(char* PostfixExpression)
{
    //...Stack 생성
    while(PostfixExpression을 끝까지 다 읽을 때까지)
    {
    	//PostfixExpression에서 토큰을 읽어내고, 읽은 토큰 크기를 Read에 누적
        Read += GetNextToken(&PostfixExpression[Position], Token, &Type);
        
        //...
        if(Type == OPERAND) //토큰이 피연산자라면 스택에 삽입
        {
        	LLS_Push(&Stack, LLS_CreateNode(Token));
        }
        else //토큰이 연산자라면 스택의 피연산자들과 함께 계산
        {
            Operator2 = LLS_Pop(&Stack);
            Operator1 = LLS_Pop(&Stack);
            
            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;
            }
            
            LLS_Push(&Stack, LLS_CreateNode(TempResult)); //연산 결과를 스택에 삽입 
         }
     }
     
     //스택에 마지막까지 남아 있는 결과값을 Result에 계산
     Result = LLS_Pop(&Stack);
     
     //...Stack 소멸 
     return Result;
}

 

2.4.3 중위 표기식을 후위 표기식으로 바꾸는 알고리즘

 

데이크스트라 알고리즘 (Dijkstra Algorithm)

 

1) 입력 받은 중위 표기식에서 토큰을 읽는다 

 

2) 토큰이 피연산자라면 토큰을 결과에 출력한다

 

3) 토큰이 연산자 (괄호 포함)라면 스택의 최상위 노드에 담긴 연산자가 토큰보다 우선순위가 높은지 검사 

 ( 검사가 끝나면 스택에는 최상위 노드보다 우선순위가 높은 연산자가 남아 있지 않게 됨)

 

  - 검사 결과가 참이면 (토큰이 최상위 노드의 연산자 보다 높으면) 최상위 노드를 스택에서 꺼내 결과에 출력하며, 

 이 검사 작업을 반복해서 수행하되 그 결과가 거짓이거나 스택이 비면 작업을 중단

  - 검사 작업이 끝난 후에는 토큰을 스택에 삽입

 

4) 토큰이 오른쪽 괄호 ')'면 최상위 노드에 왼쪽 괄호 '('가 올때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지는 않음

 

5) 중위 표기식에 더 읽을 것이 없다면 반복을 종료하고 더 읽을 것이 있다면 단계 1) 부터 다시 반복

 

ex)  (117.32 + 83) * 49을 후위 표기식으로 변환 

 

토큰	작업	출력	스택
(	스택에 '(' 삽입		(
117.32	117.32 출력	117.32	(
+	스택에 '+' 삽입	117.32	+ (
83	83 출력	117.32 83	+ (
)	스택의 모든 연산자 제거 후 출력 ( '('는 출력하지 않음)	117.32 83 +
*	스택에 '*' 삽입	117.32 83 +	*
49	49 출력	117.32 83 + 49	*
	식을 모두 읽었음. 스택의 모든 연산자 제거 후 출력	117.32 83 + 49 *

 

데이스크라의 중위- 후위 표기 변환 알고리즘을 구현한 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 += GetNextToekn( &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 ) );
       }
   }
   
   //중위 표기식을 다 읽었으니 Staxk에 남겨진 모든 연산자를 후위 표기식에 출력 
   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);
}