티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
지금부터는 후위 표기법으로의 변환 알고리즘을 코드로 구현합니다. 먼저 실제 후위 표기법으로의 변환을 처리하는 함수를 다음의 형태로 정의하기로 합니다.
void ConvToRPNExp(char exp[])
{
....
}위 함수의 의도는 다음과 같습니다.
"중위 표기법의 수식을 담고 있는 배열의 주소 값을 인자로 전달하면서 ConvToRPNExp 함수를 호출하면, 인자로 전달된 주소 값의 배열에는 후위 표기법으로 바뀐 수식이 저장된다."
(그런데 제가 잘 몰라서 그럴 수도 있지만 배열의 주소 값을 포인터로 받는 것도 아닌데 어떻게 함수 안에서 함수 밖의 변수를 변경할 수 있는 것인지 이해가 가지 않습니다. 위 함수의 매개변수는 함수 내에서 새로운 배열을 선언하는 형태를 가지고 있습니다. 위 매개변수가 인자로 전달하는 배열의 주소 값을 그대로 가질 수 있는 것인지 궁금합니다.)
따라서 함수 ConvToRPNExp는 다음의 형태로 호출이 이뤄져야 합니다.
int main(void)
{
char exp[] = "3-2+4"; //중위 표기법의 수식
ConvToRPNExp(exp); //후위 표기법의 수식으로 변환을 요청
....
return 0;
}참고로 함수 이름의 일부인 RPN은 후위 표기법의 또 다른 이름인 'Reverse Polish Notation'의 약자입니다.
ConvToRPNExp 함수의 구현에 앞서 이를 도울 다른 함수들을 먼저 정의하겠습니다. 우선은 연산자의 우선순위 정보를 반환하는 함수입니다.
int GetOpPrec(char op)
{
switch (op)
{
case '*':
case '/':
return 5; //가장 높은 우선순위
case '+':
case '-':
return 3; //5보다 낮고 1보다 높은 우선순위
case '(':
return 1; //가장 낮은 우선순위
}
return -1; //등록되지 않은 연산자임을 알림
}각각의 우선순위 값 1, 3, 5는 임의로 정한 값입니다. 이 값은 어떠한 값이 되어도 좋지만 '*'연산자나 '/'연산자는 가장 높은 우선순위, '('연산자는 가장 낮은 우선순위를 부여해야 합니다.
')'연산자의 우선순위는 부여할 필요 없습니다. 이 연산자는 (후위 표기법에서는) 스택에 저장될 일이 없기 때문입니다. 이 연산자는 그저 '('연산자가 나올 때까지 스택에 저장된 연산자를 하나씩 꺼내어 배치하라는 신호를 주는 역할에 불과합니다.
이번에는 두 연산자의 우선순위를 비교하여 결과를 반환하는 함수를 정의하겠습니다.
int WhoPrecOp(char op1, char op2)
{
int op1Prec = GetOpPrec(op1);
int op2Prec = GetOpPrec(op2);
if (op1Prec > op2Prec) return 1; //첫 번째 인자의 우선순위가 더 높다면 1 반환
else if (op1Prec < op2Prec) return -1; //두 번째 인자의 우선순위가 더 높다면 -1 반환
return 0; //두 인자의 우선순위가 같다면 0 반환
}위 함수는 첫 번째 연산자의 우선순위가 더 높으면 1, 낮으면 -1, 같으면 0을 반환합니다.
이제 이를 바탕으로 ConvToRPNExp 함수를 완성해 보겠습니다.
void ConvToRPNExp(char exp[])
{
Stack stack; //스택 생성
StackInit(&stack); //스택 초기화
int expLen = strlen(exp); //수식의 길이 저장
char* convExp = (char*)malloc(expLen + 1); //변환된 수식을 저장할 공간 동적 할당
if (convExp == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
memset(convExp, 0, sizeof(char) * expLen + 1); //변환된 수식을 저장할 공간 초기화, memset 함수에 대해서는 나중에 설명
char tok;
int index = 0;
int i;
for (i = 0; i < expLen; i++)
{
tok = exp[i];
if (isdigit(tok)) convExp[index++] = tok; //tok에 저장된 값이 10진수라면 convExp에 저장, isdigit 함수에 대해서는 나중에 설명
else
{
switch (tok)
{
case '(':
Push(&stack, tok); //여는 소괄호 '('라면 스택에 저장
break;
case ')': //닫는 소괄호 ')'라면
while (1) //반복문 실행
{
char popOp = Pop(&stack); //스택에서 데이터 하나 빼오기
if (popOp == '(') break; //스택에서 빼온 데이터가 여는 소괄호 '('라면 반복 종료
convExp[index++] = popOp; //스택에서 빼온 데이터를 convExp에 저장
}
break;
case '+':
case '-':
case '*':
case '/':
while (!IsEmpty(&stack) && WhoPrecOp(Peek(&stack), tok) >= 0) //스택이 비어있지 않고, tok의 우선순위가 스택의 연산자보다 낮다면
{
convExp[index++] = Pop(&stack); //스택에 있는 연산자를 빼서 convExp에 저장
}
Push(&stack, tok); //반복 조건에 해당되지 않으면 tok을 스택에 저장
break;
}
}
}
while (!IsEmpty(&stack)) //기존 수식의 모든 데이터를 읽은 뒤 스택이 비어 있지 않다면
{
convExp[index++] = Pop(&stack); //스택에 있는 연산자를 빼서 convExp에 저장
}
strcpy(exp, convExp); //변환이 끝난 수식을 exp에 복사
free(convExp); //동적 할당한 convExp를 삭제
}위 코드를 분석하는 것이 쉬운 일은 아님을 압니다. 하지만 인내심을 가지고 코드를 직접 따라 작성해 보면서 어떤 흐름으로 알고리즘이 진행되는지 이해하기 바랍니다. 혹시 이해되지 않는 부분이 있거나, 추가 설명이 필요하다면 언제든지 물어보길 바랍니다.
memset 함수와 isdigit 함수는 따로 정의하지도 않았는데 어디서 온 것인지 궁금하실 겁니다. 이 두 함수는 표준 함수입니다. memset 함수는 string.h 헤더 파일에 선언되어 있고, isdigit 함수는 ctype.h 헤더 파일에 선언되어 있습니다.
memset 함수는 다음과 같은 형태를 가집니다.
void* memset(void* ptr, int val, size_t len);ptr로 전달된 주소의 메모리에서부터 len 바이트를 val의 값으로 채웁니다.
isdigit 함수는 다음과 같은 형태를 가집니다.
int isdigit(int ch);ch로 전달된 문자의 내용이 10진수라면 1을 반환합니다.
이제 위와 같이 선언 및 정의된 함수들을 다음과 같은 파일로 분리하여 저장하고자 합니다.
- InfixToPostfix.h ConvToRPNExp 함수의 선언
- InfixToPostfix.c ConvToRPNExp 함수의 정의
그리고 연결 리스트로 구현한 스택과, 적절한 main 함수를 구성하여 프로그램의 실행결과를 확인해 보겠습니다.
//InfixToPostfix.h 헤더 파일로 저장
#ifndef INFIXTOPOSTFIX_H
#define INFIXTOPOSTFIX_H
void ConvToRPNExp(char exp[]);
#endif//InfixToPostfix.c 소스 파일로 저장
#include "InfixToPostfix.h"
#include "LLBStack.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int GetOpPrec(char op)
{
switch (op)
{
case '*':
case '/':
return 5; //가장 높은 우선순위
case '+':
case '-':
return 3; //5보다 낮고 1보다 높은 우선순위
case '(':
return 1; //가장 낮은 우선순위
}
return -1; //등록되지 않은 연산자임을 알림
}
int WhoPrecOp(char op1, char op2)
{
int op1Prec = GetOpPrec(op1);
int op2Prec = GetOpPrec(op2);
if (op1Prec > op2Prec) return 1; //첫 번째 인자의 우선순위가 더 높다면 1 반환
else if (op1Prec < op2Prec) return -1; //두 번째 인자의 우선순위가 더 높다면 -1 반환
return 0; //두 인자의 우선순위가 같다면 0 반환
}
void ConvToRPNExp(char exp[])
{
Stack stack; //스택 생성
StackInit(&stack); //스택 초기화
int expLen = strlen(exp); //수식의 길이 저장
char* convExp = (char*)malloc(expLen + 1); //변환된 수식을 저장할 공간 동적 할당
if (convExp == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
memset(convExp, 0, sizeof(char) * expLen + 1); //변환된 수식을 저장할 공간 초기화, memset 함수에 대해서는 나중에 설명
char tok;
int index = 0;
int i;
for (i = 0; i < expLen; i++)
{
tok = exp[i];
if (isdigit(tok)) convExp[index++] = tok; //tok에 저장된 값이 10진수라면 convExp에 저장, isdigit 함수에 대해서는 나중에 설명
else
{
switch (tok)
{
case '(':
Push(&stack, tok); //여는 소괄호 '('라면 스택에 저장
break;
case ')': //닫는 소괄호 ')'라면
while (1) //반복문 실행
{
char popOp = Pop(&stack); //스택에서 데이터 하나 빼오기
if (popOp == '(') break; //스택에서 빼온 데이터가 여는 소괄호 '('라면 반복 종료
convExp[index++] = popOp; //스택에서 빼온 데이터를 convExp에 저장
}
break;
case '+':
case '-':
case '*':
case '/':
while (!IsEmpty(&stack) && WhoPrecOp(Peek(&stack), tok) >= 0) //스택이 비어있지 않고, tok의 우선순위가 스택의 연산자보다 낮다면
{
convExp[index++] = Pop(&stack); //스택에 있는 연산자를 빼서 convExp에 저장
}
Push(&stack, tok); //반복 조건에 해당되지 않으면 tok을 스택에 저장
break;
}
}
}
while (!IsEmpty(&stack)) //기존 수식의 모든 데이터를 읽은 뒤 스택이 비어 있지 않다면
{
convExp[index++] = Pop(&stack); //스택에 있는 연산자를 빼서 convExp에 저장
}
strcpy(exp, convExp); //변환이 끝난 수식을 exp에 복사
free(convExp); //동적 할당한 convExp를 삭제
}//LLBStack.h 헤더 파일로 저장
#ifndef LLB_STACK_H
#define LLB_STACK_H
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct Node
{
Data data;
struct Node* next;
}Node;
typedef struct LLBStack
{
Node* head;
}LLBStack;
typedef LLBStack Stack;
void StackInit(Stack* pstack);
void Push(Stack* pstack, Data data);
Data Pop(Stack* pstack);
Data Peek(Stack* pstack);
int IsEmpty(Stack* pstack);
#endif//LLBStack.c 소스 파일로 저장
#include "LLBStack.h"
#include <stdlib.h>
#include <stdio.h>
void StackInit(Stack* pstack)
{
pstack->head = (Node*)malloc(sizeof(Node));
if (pstack->head == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
pstack->head->next = NULL;
}
void Push(Stack* pstack, Data data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
newNode->data = data;
newNode->next = pstack->head->next;
pstack->head->next = newNode;
}
Data Pop(Stack* pstack)
{
Node* delNode = pstack->head->next;
Node* delData = delNode->data;
pstack->head->next = delNode->next;
free(delNode);
return delData;
}
Data Peek(Stack* pstack)
{
return pstack->head->next->data;
}
int IsEmpty(Stack* pstack)
{
if (pstack->head->next == NULL) return TRUE;
return FALSE;
}//main.c 소스 파일로 저장
#include "InfixToPostfix.h"
#include <stdio.h>
int main(void)
{
char exp1[] = "1+2+3";
char exp2[] = "(1+2)*3";
char exp3[] = "((1-2)+3)*(5-2)";
ConvToRPNExp(exp1);
ConvToRPNExp(exp2);
ConvToRPNExp(exp3);
printf("%s \n", exp1);
printf("%s \n", exp2);
printf("%s \n", exp3);
return 0;
}
/*
실행결과
12+3+
12+3*
12-3+52-*
*/여기까지 중위 표기법을 후위 표기법으로 변환하는 코드를 작성했습니다. 이제 후위 표기법의 수식을 이용해 계산을 수행할 차례입니다.
본격적으로 계산을 수행하는 계산기 프로그램을 작성하기 전에 후위 표기법의 계산 방법을 설명하겠습니다. 후위 표기법에서 피연산자는 연산자 앞의 두 개의 숫자에 해당합니다.
예를 들어 다음과 같은 후위 표기법의 수식이 있다고 하면,
1 2 - 3 + 5 2 - *
첫 연산자는 '-'이고, 이 연산자를 이용해 연산되어야 하는 피연산자는 그 앞의 두 개의 숫자, 1과 2가 되는 것입니다. 그리고 이를 계산하여 결과를 반환합니다. 그러면 위 수식은 아래와 같이 됩니다.
(-1) 3 + 5 2 - *
이제는 -1과 3을 더하는 연산을 수행합니다. 그러면 수식은 아래와 같이 됩니다.
2 5 2 - *
다음 연산자는 '-'입니다. 그리고 그 앞의 두 개의 숫자 5와 2가 피연산자가 됩니다. 따라서 연산을 수행하면 수식은 아래와 같이 됩니다.
2 3 *
이제 2와 3을 곱하는 연산을 수행하면 결과는 6이 됩니다.
'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 06. 계산기 프로그램의 구현 (4) (0) | 2021.03.13 |
|---|---|
| 연습문제 06. 4 연습장을 이용해서 후위 표기법의 수식을 계산하기 (0) | 2021.03.13 |
| 연습문제 06.3 연습장을 이용해서 후위 표기법으로 바꾸기2 (0) | 2021.03.13 |
| Chapter 06. 계산기 프로그램 구현 (2) (0) | 2021.03.13 |
| 연습문제 06. 2 연습장을 이용해서 후위 표기법으로 바꾸기1 (0) | 2021.03.12 |