스택 응용하기 - 사칙연산 계산기 만들기
스택을 응용하여 '사칙 연산 계산기'를 만들어보려고 합니다. 정확히 말하자면 '수식 분석기 기반의 사칙 연산 계산기'라고도 할 수 있습니다.
계산기의 요구 조건은 간단합니다. 다음과 같이 사칙 연산 만으로 이루어진 식을 분석해서 풀 수 있으면 됩니다.
1 + 3.334 / (4.28 * (110 - 7729) )이 문제를 직접 푼다고 하면 이렇습니다. 가장 먼저 괄호 내에 있는 식을 풀 것입니다. 괄호가 중첩되어 있다면 가장 안쪽에 있는 괄호부터 풀 것입니다. 그리고 곱셈(*)과 나눗헴(/)을, 그 후에 덧셈과 뺄셈 계산을 할 것입니다.
하지만 이는 사람이기에 할 수 있는 계산입니다. 컴퓨터는 이와 같은 방법으로 계산할 수가 없습니다. 따라서 컴퓨터가 이 문제를 풀도록 만들려면 컴퓨터가 사용할 알고리즘을 제공해야 합니다.
이후 자세히 설명할 것이지만, 이 알고리즘이 동작하는 원리에 대해 간단히 설명하자면 우선 수식을 프로그램이 풀기에 적당한 형식으로 변환한 다음, 변환된 수식을 프로그램이 계산하는 과정으로 동작합니다. 여기에서 스택은 수식을 다른 형식으로 변환할 때, 그리고 변환된 수식을 계산할 때에 사용됩니다.
수식을 변환하기 위해서는 수식의 중위 표기법, 후위 표기법에 대해 잘 이해하고 있어야 합니다.
수식의 중위 표기법과 후위 표기법
다음 식의 결과를 계산할 수 있으시나요?
1 2 33 / + 9 13 * -무언가 이상해보이지만 위의 식은 엄연히 계산이 가능한 수식입니다. 이 식의 결과는 다음의 식과 같습니다.
1 + 2 / 33 - 9 * 13전자는 후위 표기법(Postfix Notation)으로 수식을 표현한 것이고, 후자는 일반적으로 많은 사람들이 이용하는 중위 표기법(Infix Notation)으로 표현한 것입니다.
후위 표기법은 역(易) 폴리쉬 표기법(Reverse Polish Notation)이라고도 하며, 호주의 찰스 햄블린이 1950년대 중반에 개발한 알고리즘입니다. 이 표기법의 규칙은 연산자를 피연산자 뒤에 위치시키는 것입니다. 그렇기 때문에 '후위' 표기법 입니다. 반면 중위 표기법은 연산자가 피연산자 가운데에 위치하는 것이 규칙입니다.
다음은 중위 표기법과 후위 표기법의 몇 가지 예시입니다.
| 중위 표기법 | 후위 표기법 |
|---|---|
| 1 + 3 | 1 3 + |
| 23 / 7 + 12 | 23 7 / 12 + |
| (117.32 + 83) * 49 | 117.32 83 + 49 * |
| 1 - 3 * 2 | 1 3 2 * - |
후위 표기식을 계산하는 알고리즘
후위 표기식을 계산하는 알고리즘은 두 가지 규칙으로 이루어져 있습니다. 예를 들어 후위 표기식 1 3 2 * -(중위 표기법으로는 1 - 3 * 2)를 풀어보도록 하겠습니다.
| 1 | 3 | 2 | * | - |
후위 표기식 계산 알고리즘의 첫 번째 규칙은 식의 왼쪽부터 요소를 읽어내면서 피연산자는 스택에 담는 것입니다. 처음 나오는 요소 '1'은 피연산자이므로 스택에 삽입합니다.
| 1 | 3 | 2 | * | - |
< 스 택 >
| 1 |두 번째 요소도 피연산자이므로 스택에 삽입합니다. 이제 스택은 1, 3 두 개의 요소를 담고 있습니다.
| 1 | 3 | 2 | * | - |
< 스 택 >
| 3 |
| 1 |세 번째 요소도 피연산자이고 역시 스택에 삽입합니다.
| 1 | 3 | 2 | * | - |
< 스 택 >
| 2 |
| 3 |
| 1 |여기까지 했으면 두 번째 규칙을 설명드리겠습니다. 두 번째 규칙은 연산자가 나타난 경우에 스택에서 피연산자 두 개를 꺼내어 연산을 실행하고 그 연산 결과를 다시 스택에 삽입하는 것입니다. 네 번째 요소는 곱셈을 수행하는 * 이므로 스택에서 두 번의 제거 연산을 수행하여 피연산자 2 와 3을 꺼낸 후 3 * 2 의 결과 6을 스택에 삽입합니다. 그 결과 스택에는 1과 6이 저장됩니다.
| 1 | 3 | 2 | * | - |
< 스 택 >
→ | 2 | 제거
→ | 3 | 제거
| 6 | ← 3 * 2 의 결과를 삽입
| 1 |다섯 번째 요소는 - 입니다. 연산자를 만났을 때에는 2회의 제거 연산을 실행하여 피연산자 두 개를 꺼내어 계산을 수행한다고 앞서 설명했습니다. 6과 1을 꺼낸 후 1 - 6의 결과 - 5를 스택에 저장합니다.
| 1 | 3 | 2 | * | - |
< 스 택 >
→ | 6 | 제거
→ | 1 | 제거
| - 5 | ← 1 - 6 의 결과를 삽입 이렇게 하여 식을 모두 읽었고 스택에는 식의 최종 계산 결과만 남게 됩니다. 이 값을 스택에서 꺼내면 계산 결과를 얻는 것입니다.
다음은 후위 표기식을 계산하는 함수의 뻐대만 작성한 것입니다. 실제 구현에 비하면 많은 것이 생략되어있지만, 주요한 내용은 존재합니다.
double Calculate( char* PostfixExpression )
{
/* ... Stack 생성 */
while ( PostfixExpression을 끝까지 다 읽을 때까지 )
{
/* PostfixExpression에서 토큰을 읽어내고, 읽은 토큰 크기를 Read에 누적 */
Read += GetNextToken( &PostfixExpression[Read], 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;
}중위 표기법에서 후위 표기법으로의 변환 알고리즘
이 알고리즘은 위대한 수학자이자 프로그래머였던 애드거 다익스트라(Edsger Dijkstra)가 고안한 알고리즘입니다. 동작과정은 다음과 같습니다.
- 입력받은 중위 표기식에서 토큰을 읽는다.
- 토큰이 피연산자이면 토큰을 결과에 출력한다.
- 토큰이 연산자(괄호 포함)일 경우, 스택의 최상위 노드에 담겨있는 연산자가 토큰보다 우선 순위가 높은지 여부를 검사한다. 검사 결과가 참이면 최상위 노드를 스택에서 꺼내어 결과에 출력하고, 이 검사 작업을 반복하여 수행하되 그 결과가 거짓이거나 스택이 비게 되면 작업을 중단한다. 검사 작업이 끝난 이후에는 토큰을 스택에 삽입한다. (이로 인해 스택에는 최상위 노드보다 우선순위가 높은 연산자는 존재하지 않게 된다.)
- 토큰이 오른쪽 괄호
)이면 최상위 노드에 왼쪽 괄호(가 올 때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지는 않는다. - 중위 표기식에 더 읽을 것이 없으면 빠져나가고 더 읽을 것이 있다면 1부터 다시 반복한다.
이 알고리즘을 토대로 중위 표기식을 후위 표기식으로 변환해봅니다.
(117.32 + 83) * 49
예를 들어 이 식을 후위 표기식으로 변환하는 과정은 다음과 같습니다.
| 토큰 | 작업 | 출력 | 스택 |
|---|---|---|---|
| ( 117.32 + 83 ) * 49 | 스택에 ( 삽입 |
( |
|
| ( 117.32 + 83 ) * 49 | 117.32 출력 |
117.32 | ( |
| ( 117.32 + 83 ) * 49 | 스택에 + 삽입 |
117.32 | + ( |
| ( 117.32 + 83 ) * 49 | 83 출력 |
117.32 83 | + ( |
| ( 117.32 + 83 ) * 49 | 스택의 모든 연산자가 제거 후 출력((는 출력 안함) |
117.32 83 + | |
| ( 117.32 + 83 ) * 49 | 스택에 * 삽입 |
117.32 83 + | * |
| ( 117.32 + 83 ) * 49 | 49 출력 |
117.32 83 + 49 | * |
| ( 117.32 + 83 ) * 49 | 식 모두 읽었으므로, 스택의 모든 연산자 제거 후 출력 | 117.32 83 + 49 * |
아래의 코드는 다익스트라의 중위-후위 표기 변환 알고리즘을 구현한 GetPostfix() 함수입니다.
void GetPostfix( char* InfixExpression, char* PostfixExpression )
// InfixExpression: 중위 표기식 / 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) ) // 중위 표기식을 다 읽었으니 Stack에 남겨져 있는 모든 연산자를 후위 표기식에 출력
{
Node* Popped = LLS_Pop( Stack );
if ( Popped->Data[0] != LEFT_PARENTHESIS )
strcat( PostfixExpression, Popped->Data );
LLS_DestroyNode( Popped );
}
LLS_DestroyStack(Stack);
}사칙 연산 계산기 예제 프로그램
예제는 모두 다섯 개의 파일로 구성되어 있습니다.
LinkedListStack.h와LinkedListStack.c▶ 링크드 리스트 기반의 스택이 구현되어 있음Calculator.h와Calculator.c▶ 중위 표기식을 후위 표기식으로 변환하는 알고리즘과 후위 표기식을 계산하는 알고리즘Test_Calculator.c▶ 사용자가 중위 표기식을 입력하면 Calculator.h와 Caculator.c에 구현되어 있는 함수를 토대로 결과를 계산하여 출력
LinkedListStack.h 와 LinkedListStack.c 는 아래 링크해둔 포스팅에서 참고하여 사용하시면 됩니다.
링크드 리스트로 구현하는 스택
링크드 리스트로 구현하는 스택 링크드 리스트로 스택을 구현하면 스택의 용량에 제한을 두지 않아도 된다는 장점이 있습니다. 링크드 리스트의 구조를 잘 떠올리며 링크드 스택에 대해 알아보
likewiki.site
Calculator.h
#ifndef CALCULATOR_H
#define CALCULATOR_H
#include <stdlib.h>
#include "LinkedListStack.h"
typedef enum
{
LEFT_PARENTHESIS = '(', RIGHT_PARENTHESIS = ')',
PLUS = '+', MINUS = '-',
MULTIPLY = '*', DIVIDE = '/',
SPACE = ' ', OPERAND
} SYMBOL;
int IsNumber( char Cipher );
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 CALCULATOR_HCalculator.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;
}Test_Calculator.c
#include <stdio.h>
#include <string.h>
#include "Calculator.h"
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;
}'IT > 알고리즘' 카테고리의 다른 글
| 큐 (Queue) - 큐의 주요 기능, 순환 큐 (0) | 2020.07.15 |
|---|---|
| 링크드 리스트로 구현하는 스택 (0) | 2020.07.01 |
| 스택(Stack)의 개념 및 배열로 구현하는 스택 (0) | 2020.06.26 |
| 환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List) (0) | 2020.06.25 |
| 더블 링크드 리스트(Doubly Linked List) (0) | 2020.06.23 |
