<Stack 관련 구현>
[ListBaseStack.h]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: ListBaseStack.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현
* 이전 버전 내용:
*/
#ifndef __LIST_BASE_STACK_H__
#define __LIST_BASE_STACK_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node* next;
} Node;
typedef struct _liststack
{
Node* head;
} ListStack;
typedef ListStack Stack;
void StackInit(Stack* pstack);
int SisEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data SPeek(Stack* pstack);
#endif
[ListBaseStack.c]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: ListBaseStack.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현
* 이전 버전 내용:
*/
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"
void StackInit(Stack* pstack)
{
pstack->head = NULL;
}
int SisEmpty(Stack* pstack)
{
if (pstack->head == NULL)
return TRUE;
else
return FALSE;
}
void SPush(Stack* pstack, Data data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->next = pstack->head;
pstack->head = newNode;
}
Data SPop(Stack* pstack)
{
Node* pNode;
Data pData;
if (SisEmpty(pstack))
{
printf("Stack is Empty\n");
exit(-1);
}
pNode = pstack->head;
pData = pNode->data;
pstack->head = pstack->head->next;
free(pNode);
return pData;
}
Data SPeek(Stack* pstack)
{
if (SisEmpty(pstack))
{
printf("Stack is Empty\n");
exit(-1);
}
return pstack->head->data;
}
<중위 표기법에서 후위 표기법으로 변환>
[InfixToPostfix.h]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: InfixToPostfix.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현
* 이전 버전 내용:
*/
#ifndef __INFIX_TO_POSTFIX_H__
#define __INFIX_TO_POSTFIX_H__
// 중위 -> 후위 표기법으로 변환하는 함수
void ConvToRPNExp(char exp[]); // RPN -> Reverse Polish Notation, 후위 표기법 영문
#endif
[InfixToPostfix.c]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: InfixToPostfix.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현
* 이전 버전 내용:
*/
#define _CRT_SECURE_NO_WARNINGS
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "ListBaseStack.h"
// 연산자 우선 순위를 부여
int GetOpPrec(char op)
{
switch (op)
{
// 곱셈과 나눗셈이 우선 순위가 가장 높고
case '*':
case '/':
return 5;
// 덧셈과 뺄셈이 그 다음으로 우선 순위가 높고
case '+':
case '-':
return 3;
// 여는 소괄호의 우선 순위가 가장 낮다.
// 닫는 괄호는 연산자 우선순위를 신경쓸 필요가 없다.
// 만나는 순간 스택에 쌓아놨던 것을 다 pop 처리하므로
case '(':
return 1;
}
return -1; // 연산자가 아닌 다른 것이 들어올 경우에는 에러 처리를 위해 -1 반환
}
// 스택에 들어가는 연산자의 우선 순위 비교
int WhoPrecOp(char op1, char op2)
{
int op1Prec = GetOpPrec(op1);
int op2Prec = GetOpPrec(op2);
if (op1Prec > op2Prec)
return 1;
else if (op1Prec < op2Prec)
return -1;
else
return 0;
}
// 중위 -> 후위 표기법으로 변환하는 함수
void ConvToRPNExp(char exp[]) // RPN -> Reverse Polish Notation, 후위 표기법 영문
{
Stack stack; // 연산자를 담을 스택
int expLen = strlen(exp); // 입력받은 수식의 길이
char* convExp = (char*)malloc((sizeof(char) * expLen) + 1); // 후위 표기식이 담길 배열 동적 할당
int i, idx = 0; // 수식 배열에 쓰일 인덱스 i와 후위 표기식의 인덱스 idx
char tok, popOp; // 입력받은 수식의 토큰(tok)과 스택에서 pop된 연산자를 담을 변수(popOp)
memset(convExp, 0, (sizeof(char) * expLen + 1)); // 동적할당한 배열의 메모리 공간을 0으로 초기화
StackInit(&stack); // stack 초기화
// 입력 받은 수식을 토큰으로 나눠서 반복 수행
for (i = 0; i < expLen; i++)
{
tok = exp[i];
if (isdigit(tok)) // 입력된 토큰이 숫자(피연산자)라면
{
convExp[idx++] = tok; // 변환된 수식에 저장
}
else // 연산자라면 스택에 담는 과정 수행
{
switch (tok)
{
case '(': // '('일 경우 무조건 스택에 들어간다
SPush(&stack, tok);
break;
case ')': // ')'일 경우, '('을 만날때까지 스택에 담겨있던 연산자를 모두 pop한다.
while (1)
{
popOp = SPop(&stack);
if (popOp == '(') // 마지막으로 pop된 연산자가 '('라면 pop을 중단
break;
convExp[idx++] = popOp; // 후위 표기식에 연산자를 저장
}
break;
// 나머지 '+', '-', '*', '/' 에 대한 처리
case '+':
case '-':
case '*':
case '/':
// 두 개의 조건 동시에 만족하는 상황 동안 반복문을 수행.
// 1. 스택이 비어있지 않음
// 2. 현재 스택의 가장 위에 있는 연산자와 현재 연산자를 비교해서 0보다 크거나 같다
// 2의 경우, 스택에 담겨 있는 연산자의 우선순위가 같거나 더 높은 경우에 Pop을 수행한다.
while (!SisEmpty(&stack) && WhoPrecOp(SPeek(&stack), tok) >= 0)
convExp[idx++] = SPop(&stack);
// 그리고 연산자를 스택에 저장
SPush(&stack, tok);
break;
}
}
}
// 위의 과정이 다 끝나면 마지막으로 스택에 남은 연산자를 전부 Pop한다.
while (!SisEmpty(&stack))
convExp[idx++] = SPop(&stack);
strcpy(exp, convExp); // 변환된 후위 표기식을 exp에 복사하고
free(convExp); // 할당한 메모리를 해제한다.
}
<후위 표기법 수식 계산>
[PostCaculator.h]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: PostCaculator.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 후위 표기식을 계산하는 프로그램의 구현
* 이전 버전 내용:
*/
#ifndef __POST_CALCULATOR_H__
#define __POST_CALCULATOR_H__
// 후위 표기법의 수식을 계산한 결과를 반환하는 함수
int EvalRPNEXP(char exp[]);
#endif
[PostCaculator.c]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: PostCaculator.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 후위 표기식을 계산하는 프로그램의 구현
* 이전 버전 내용:
*/
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
// 후위 표기법의 수식을 계산한 결과를 반환하는 함수
int EvalRPNEXP(char exp[])
{
Stack stack; // 마찬가지로 계산에서도 스택을 사용.
int expLen = strlen(exp); // 입력받은 후위 표기식의 길이
int i; // 반복문에 사용될 인자
char tok, op1, op2; // 입력받은 후위 표기식의 토큰(tok)과 피연산자 변수를 담기 위한 op1, op2
StackInit(&stack); // 스택의 초기화
for (i = 0; i < expLen; i++)
{
tok = exp[i]; // 입력받은 후위표기식을 토큰으로 하나하나 받는다.
if (isdigit(tok)) // 피연산자(숫자)라면
{
SPush(&stack, tok - '0'); // 입력받은 문자를 숫자로 바꾸기 위해 문자'0'과의 차(실제 정수값을 구하기 위해)를 구해서 stack에 저장.
}
else // 연산자라면
{
op2 = SPop(&stack); // 두 번째 피연산자를 스택에서 꺼내고
op1 = SPop(&stack); // 첫 번째 피연산자를 스택에서 꺼낸다
// 연산자의 종류에 따라 두 연산자에 대한 연산값을 계산하고 다시 스택에 넣는다
switch (tok)
{
case '+':
SPush(&stack, op1 + op2);
break;
case '-':
SPush(&stack, op1 - op2);
break;
case '*':
SPush(&stack, op1 * op2);
break;
case '/':
SPush(&stack, op1 / op2);
break;
}
}
}
return SPop(&stack); // 마지막으로 계산된 값(최종 값)을 return한다.
}
<모든 과정을 하나로 통합>
[InfixCaculator.h]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: InfixCaculator.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 중위 표기법 수식 -> 후위 표기법 수식 변환 -> 후위 표기법 수식 계산 -> 계산 결과 프로그램 통합
* 이전 버전 내용:
*/
#ifndef __INFIX_CALCULATOR_H__
#define __INFIX_CALCULATOR_H__
// 중위 표기법 수식 -> 후위 표기법 수식 변환 -> 후위 표기법 수식 계산 -> 계산 결과 반환
// 이 모든걸 하나에 담는 함수
int EvalInfixExp(char exp[]);
#endif
[InfixCaculator.c]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: InfixCalculator.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 중위 표기법 수식 -> 후위 표기법 수식 변환 -> 후위 표기법 수식 계산 -> 계산 결과 프로그램 통합
* 이전 버전 내용:
*/
#define _CRT_SECURE_NO_WARNINGS
#include <string.h>
#include <stdlib.h>
#include "InfixToPostfix.h" // 후위 표기식 변환에 사용
#include "PostCalculator.h" // 후위 표기식 계산에 사용
#include "InfixCalculator.h"
// 중위 표기법 수식 -> 후위 표기법 수식 변환 -> 후위 표기법 수식 계산 -> 계산 결과 반환
// 이 모든걸 하나에 담는 함수
int EvalInfixExp(char exp[])
{
int len = strlen(exp); // 입력 받은 수식의 길이
int ret; // 계산 결과를 받을 변수
char* expcpy = (char*)malloc((sizeof(char) * len) + 1); // 입력 받은 수식을 복사하기 위한 배열 동적할당
strcpy(expcpy, exp);
ConvToRPNExp(expcpy); // 후위 표기식으로 변환
ret = EvalRPNEXP(expcpy); // 변환된 후위 표기식을 계산하여 계산 결과를 저장
free(expcpy); // 동적 할당 했던 메모리를 해제하고
return ret; // 결과를 반환
}
<결과 확인용 main>
[InfixCaculatorMain.c]
/*
* 선형 자료구조 - 연결 리스트 기반 Stack 계산기 v0.3
* 파일명: InfixCaculatorMain.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-23
* 이전 버전 작성 일자:
* 버전 내용: 중위 표기법 수식 -> 후위 표기법 수식 변환 -> 후위 표기법 수식 계산 -> 계산 결과 프로그램 통합
* 이전 버전 내용:
*/
#include <stdio.h>
#include "InfixCalculator.h"
int main()
{
char exp1[] = "1+2*3";
char exp2[] = "(1+2)*3";
char exp3[] = "((1-2)+3)*(5-2)";
printf("%s = %d\n", exp1, EvalInfixExp(exp1));
printf("%s = %d\n", exp2, EvalInfixExp(exp2));
printf("%s = %d\n", exp3, EvalInfixExp(exp3));
return 0;
}
스택 구현까지는 따로 공부를 했었는데, 진도만 나가겠다고 미뤄뒀던 스택 계산기 구현을 끝냈다.
따로 내가 로직을 짜거나 하진 않았고 책에 있는 설명과 코드를 보면서 최대한 주석을 달아가며 코드를 작성하였다.
학부생 때도 만들어봤던거지만 막상 다시해보니까 또 느낌이 남다르다.
그때는 학점만 잘 받겠다고 그냥 복사하고 붙여넣기만하고 결과만 잘 나오는지 확인만 했었던 때였으니까.
지금은 공부한다는 차원에서 접근하니까 코드가 새롭게 보이기도 한다.
