Rootable의 개발일기
C 계산기 구현 본문
🚩 학습 목표
✔ 연결 리스트 자료 구조 사용
✔ 구조체 노드 생성
✔ 포인터를 통한 데이터 접근
✔ 계산기 구현
✍ 연결 리스트
여러 데이터를 앞 뒤로 포인터를 통해 사슬처럼 연결할 수 있는 자료구조
🔎 특징
- 연속되는 항목들이 포인터로 연결되어 있음
- 마지막 항목은 NULL을 가리킴
- 프로그램이 수행되는 동안 크기가 동적으로 변함
- 메모리 공간 낭비가 적지만 포인터 메모리가 필요함
- 배열보다 데이터 추가와 삭제, 삽입 등 용이
- 순차 접근을 해기 때문에 탐색 속도가 떨어짐
- 데이터는 객체 단위로 추가함
- head의 링크를 끊어버리면 전체 노드를 삭제할 수 있음
🔨 구현
✅ 선언
typedef struct
{
double item;
struct Node *ptr;
} Node;
위와 같은 식으로 선언할 수 있다. 하지만 아직 메모리를 할당하지 않았기 때문에 실제로 생성되지는 않은 상태다.
✅ Head 선언
가장 첫 번째 노드가 될 head 노드부터 생성한다.
Node *head = NULL;
✅ 메모리 및 데이터 할당
head = (Node *)malloc(sizeof(Node));
head->item = 10;
head->ptr = NULL;
✅ 연결
Node *node = NULL;
node = (Node *)malloc(sizeof(Node));
node->item = 20;
node->ptr = NULL;
head->ptr = node;
✍ 구조체
다양한 데이터 조합을 지원하기 위해 변수들의 집합을 하나의 타입으로 나타낸 것
✅ 정의와 선언
struct Product
{
int id;
char *name;
int price;
};
또는 아래와 같이 익명으로 선언한 후 뒤에 typedef를 통해 별칭을 달아줄 수도 있다.
typedef struct
{
int id;
char *name;
int price;
}Product;
✅ 구조체 멤버 접근
int main()
{
Product product1;
// 초기화 - 방법 1
product1.id = 1;
product1.name = "Server";
product1.price = 50000;
// 초기화 - 방법 2
Product product2 = {.id = 1, .name = "Server", .price = 50000};
// 초기화 - 방법 3
Product product3 = {1, "Server", 50000};
printf("id: %d\n", product1.id);
printf("name: %s\n", product1.name);
printf("price: %d\n", product1.price);
return 0;
}
🔎 중첩 구조체
구조체 내 구조체를 선언할 수 있다. 본인이 설계하고자 하는 객체에 따라 사용할 수 있다.
🔸 외부 참조 구조체
struct score
{
double math;
double english;
double total;
double average;
};
struct student
{
int no;
struct score s;
};
int main(void)
{
struct student stu = {20170121, {90, 80, 0, 0}};
stu.s.total = stu.s.math + stu.s.english;
stu.s.average = stu.s.total / 2;
printf("학번 : %d\n", stu.no);
printf("총점 : %lf\n", stu.s.total);
printf("평균 : %lf\n", stu.s.average);
return 0;
}
🔸 자기 참조 구조체
#include <stdio.h>
typedef struct student
{
char name[20];
int money;
struct student *link;
} Student_List;
int main(void)
{
Student_List stu1 = {"박효원", 5000, NULL};
Student_List stu2 = {"라태인", 6000, NULL};
Student_List stu3 = {"강건욱", 4000, NULL};
stu1.link = &stu2;
stu2.link = &stu3;
printf("%s %d\n", stu1.name, stu1.money);
printf("%s %d\n", stu1.link->name, stu1.link->money);
printf("%s %d\n", stu1.link->link->name, stu1.link->link->money);
return 0;
}
위 코드를 보면 stu1 -> stu2 -> stu3 식으로 참조를 할 수 있다. 이는 연결 리스트와 유사한 구조를 가진다.
🎨 계산기
📜 구현 개요
1. 모든 입력 값은 노드이며, 노드들을 연결리스트로 묶음
2. Stack 구조를 사용하므로, 연결리스트에 노드가 추가될 때마다 바로 앞 노드를 가리킨다.
3. Stack 구조로 계산하기 위해서 입력된 수식을 후위변환식으로 변경한다.
4. 변환된 후위식에서 계산할 피연산자 단위를 구분하기 위해 strtok을 구현한다.
5. 계산을 통해 계산 결과를 출력한다. 이때, 소수점 3자리까지만 출력한다.
📌 연결리스트 및 구조체 선언
typedef struct
{
double item;
struct Node *link;
} Node;
typedef struct
{
Node *head;
} LinkedList;
각 노드는 item이라는 값과 이전 노드를 가리키는 link를 가진다.
LlinkedList는 초기 head 역할을 하는 구조체로 head라는 포인터를 통해 노드를 연결하고 해제한다.
또한 아래와 같이 초기화를 할 수 있다.
void init(LinkedList *L)
{
L->head = NULL;
}
📌 스택 관련 함수
int isEmpty(LinkedList *L)
{
return (L->head == NULL);
}
void push(LinkedList *L, double item)
{
Node *node = (Node *)malloc(sizeof(Node)); // 새 노드 메모리 할당
// 기존 노드와 연결
node->item = item; // 노드 값 셋팅
node->link = (L->head); // 새 노드 -> 기존 노드
(L->head) = node; // 맨 앞 노드이므로 head로 변경
}
double pop(LinkedList *L)
{
if (isEmpty(L))
{
printf("StackIsEmpty Error\n");
exit(1);
}
else
{
Node *node = L->head; // node: 가장 최근에 연결된 노드
double item = node->item; // 반환할 값
L->head = L->head->link; // 바로 앞에 위치한 노드가 head가 됨
free(node);
return item;
}
}
double peek(LinkedList *L)
{
if (isEmpty(L))
{
printf("StackIsEmpty Error\n");
exit(1);
}
else
{
return L->head->item; // 가장 뒷 노드의 값 리턴
}
}
push를 하게 되면 아래와 같은 그림이 된다.
push 과정
- 새 노드를 생성(메모리 할당)한다.
- 새 노드에 값을 세팅
- 새 노드는 head(앞 노드)를 가리킨다.
- 새 노드가 새로운 head가 된다.
pop 은 아래와 같이 동작한다. head를 통해 새 노드가 연결되기 때문에 head를 변경하고 메모리를 해제해 주면 된다.
pop 과정
- 기존 head의 값과 주소 저장
- head를 앞 노드로 변경
- 메모리 해제
- 값 반환
📌 후위 변환
void toPostfix(char exp[], char postfix[])
{
int p = 0; // p : postfix 배열 인덱스
int len = cstrlen(exp);
char ch;
Node *node = NULL;
init(&node);
for (int i = 0; i < len; i++)
{
ch = exp[i];
switch (ch)
{
case '*':
case '/':
case '+':
case '-':
while (!isEmpty(&node) && priority(ch) <= priority(peek(&node)))
{
postfix[p++] = ' ';
postfix[p++] = pop(&node);
}
push(&node, ch);
break;
case '(':
push(&node, ch);
break;
case ')':
while (!isEmpty(&node) && peek(&node) != '(') // find '('
{
postfix[p++] = ' ';
postfix[p++] = pop(&node);
}
pop(&node); //'(' 제거
break;
default: // digit
if (i > 0 && exp[i - 1] - 48 < 0) // 수식 숫자 앞 연산자 -> 공백
{
postfix[p++] = ' ';
}
postfix[p++] = ch;
break;
}
}
while (!isEmpty(&node))
{
postfix[p++] = ' ';
postfix[p++] = pop(&node);
}
}
먼저 문자 배열로 받은 수식을 하나씩 처리하도록 했다.
수식은 크게 연산자, 피연산자, 괄호로 나누어 볼 수 있다.
후위표현식을 만드는 규칙은 다음과 같다.
- 모든 값은 공백으로 구분할 것이기 때문에 후위식 배열(postfix)에 넣기 전에 추가한다.
- 모든 숫자는 바로 후위식 배열에 담는다.
- 딘, 2자리 이상 숫자를 처리하기 위해 수식의 숫자 이전 자리에 연산자가 있을 때만 공백을 넣는다.
- '('는 스택(연결리스트)에 담는다.
- 사칙 연산자는 스택이 비지 않았고, 현재 연산자 우선순위가 앞에 들어간 연산자보다 같거나 낮을 경우 앞에 들어간 연산자를 후위식 배열에 추가하고 현재 연산자를 스택에 추가한다.
- 연산자 우선순위가 높은 것이 먼저 계산되어야 하기 때문에 후위식 배열에 먼저 들어간 것이다.
- ')' 연산자는 '(' 연산자를 찾을 때까지 스택을 탐색하면서 연산자를 후위식 배열로 옮긴다.
- '('을 제거해야 하기 때문에 탐색 후 pop을 한번 더 수행한다.
- 수식의 마지막은 숫자다. 그래서 처리가 끝난 후에 스택에 연산자가 반드시 남는다.
- 반복문을 통해 남은 연산자를 후위식 배열로 옮긴다.
📌 계산
int cstrlen(char *str)
{
int idx = 0;
while (str[idx] != '\0')
++idx;
return idx;
}
char *cstrtok(char *postfix, char *delim)
{
char *start = 0; // 문자열 시작 위치
int i = 0;
static char *tmp; // 문자열 주소 저장
if (postfix != NULL) // 첫 토큰 받을 때
start = postfix;
else // 두 번째 이후 토큰 받을 때
start = tmp;
if (cstrlen(start) < 1) // 문자열 종료
return NULL;
for (i = 0; i < cstrlen(start); i++)
{
if (start[i] == (*delim) || start[i] == '\0')
{
start[i] = '\0';
break;
}
}
tmp = &start[i + 1]; // 다음 배열 시작 위치
return start;
}
cstrtok은 strtok을 구현한 것이다.
strtok과 같이 동작하도록 처음 호출했을 때(postfix != NULL)는 첫 문자열을 가리키도록 하고, 공백 또는 NULL을 찾을 때마다 NULL로 대체한다.
start라는 포인터를 이동하면서 공백을 기준으로 나누어진 토큰을 가리킨다. tmp는 다음 토큰의 포인터를 저장하기 위한 임시 포인터다.
double calculate(char postfix[])
{
int len = cstrlen(postfix);
double op1 = 0.0, op2 = 0.0;
Node *node = NULL;
char *delim = " ";
char *token;
init(&node);
token = cstrtok(postfix, delim);
while (token != NULL)
{
printf("token: %s\n", token);
if (token[0] != '*' && token[0] != '/' && token[0] != '+' && token[0] != '-')
{
int i = 0;
double val = 0.0; // 두자리 수 이상 결과
// 각 토큰 -> 스택 저장
while (token[i] != '\0')
{
val = val * 10 + (token[i] - 48);
i++;
}
push(&node, val);
}
else
{
op2 = pop(&node);
op1 = pop(&node);
switch (token[0])
{
case '+':
push(&node, op1 + op2);
break;
case '-':
push(&node, op1 - op2);
break;
case '*':
push(&node, op1 * op2);
break;
case '/':
if (op2 == 0) // 나누기 0 예외 처리
printf("DivideByZeroException\n");
push(&node, op1 / op2);
break;
}
}
token = cstrtok(NULL, delim);
}
return pop(&node);
}
변환된 후위식은 공백을 기준으로 연산자와 피연산자가 들어 있다. 여기서 공백을 제거한 연산자와 피연산자만을 가지는 포인터가 token이다.
후위식 계산은 숫자일 때는 스택에 넣고, 연산자가 나오면 숫자를 2개 pop()하여 해당 연산자에 맞는 작업을 하면 된다. 여기서 0으로 나누는 경우를 예외 처리했고, 2자리 이상 숫자일 경우 해당 숫자를 만들도록 했다.
📌 전체 코드
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
double item;
struct Node *link;
} Node;
typedef struct
{
Node *head;
} LinkedList;
void init(LinkedList *L)
{
L->head = NULL;
}
int isEmpty(LinkedList *L)
{
return (L->head == NULL);
}
void push(LinkedList *L, double item)
{
Node *node = (Node *)malloc(sizeof(Node)); // 새 노드 메모리 할당
// 기존 노드와 연결
node->item = item; // 노드 값 셋팅
node->link = (L->head); // 새 노드 -> 기존 노드
(L->head) = node; // 맨 앞 노드이므로 head로 변경
}
double pop(LinkedList *L)
{
if (isEmpty(L))
{
printf("StackIsEmpty Error\n");
exit(1);
}
else
{
Node *node = L->head; // node: 가장 최근에 연결된 노드
double item = node->item; // 반환할 값
L->head = L->head->link; // 바로 앞에 위치한 노드가 head가 됨
free(node);
return item;
}
}
double peek(LinkedList *L)
{
if (isEmpty(L))
{
printf("StackIsEmpty Error\n");
exit(1);
}
else
{
return L->head->item; // 가장 뒷 노드의 값 리턴
}
}
int priority(char op)
{
switch (op)
{
case '(':
case ')':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return -1;
}
int cstrlen(char *str)
{
int idx = 0;
while (str[idx] != '\0')
++idx;
return idx;
}
char *cstrtok(char *postfix, char *delim)
{
char *start = 0; // 문자열 시작 위치
int i = 0;
static char *tmp; // 문자열 주소 저장
if (postfix != NULL) // 첫 토큰 받을 때
start = postfix;
else // 두 번째 이후 토큰 받을 때
start = tmp;
if (cstrlen(start) < 1) // 문자열 종료
return NULL;
for (i = 0; i < cstrlen(start); i++)
{
if (start[i] == (*delim) || start[i] == '\0')
{
start[i] = '\0';
break;
}
}
tmp = &start[i + 1]; // 다음 배열 시작 위치
return start;
}
double cround(double num, int place)
{
for (int i = 1; i < place; i++)
{
num *= 10;
}
num += 0.5;
for (int i = 1; i < place; i++)
{
num /= 10;
}
return num;
}
void toPostfix(char exp[], char postfix[])
{
int p = 0; // p : postfix 배열 인덱스
int len = cstrlen(exp);
char ch;
Node *node = NULL;
init(&node);
for (int i = 0; i < len; i++)
{
ch = exp[i];
switch (ch)
{
case '*':
case '/':
case '+':
case '-':
while (!isEmpty(&node) && priority(ch) <= priority(peek(&node)))
{
postfix[p++] = ' ';
postfix[p++] = pop(&node);
}
push(&node, ch);
break;
case '(':
push(&node, ch);
break;
case ')':
while (!isEmpty(&node) && peek(&node) != '(') // find '('
{
postfix[p++] = ' ';
postfix[p++] = pop(&node);
}
pop(&node); //'(' 제거
break;
default: // digit
if (i > 0 && exp[i - 1] - 48 < 0) // 수식 숫자 앞 연산자 -> 공백
{
postfix[p++] = ' ';
}
postfix[p++] = ch;
break;
}
}
while (!isEmpty(&node))
{
postfix[p++] = ' ';
postfix[p++] = pop(&node);
}
}
double calculate(char postfix[])
{
int len = cstrlen(postfix);
double op1 = 0.0, op2 = 0.0;
Node *node = NULL;
char *delim = " ";
char *token;
init(&node);
token = cstrtok(postfix, delim);
while (token != NULL)
{
printf("token: %s\n", token);
if (token[0] != '*' && token[0] != '/' && token[0] != '+' && token[0] != '-')
{
int i = 0;
double val = 0.0; // 두자리 수 이상 결과
// 각 토큰 -> 스택 저장
while (token[i] != '\0')
{
val = val * 10 + (token[i] - 48);
i++;
}
push(&node, val);
}
else
{
op2 = pop(&node);
op1 = pop(&node);
switch (token[0])
{
case '+':
push(&node, op1 + op2);
break;
case '-':
push(&node, op1 - op2);
break;
case '*':
push(&node, op1 * op2);
break;
case '/':
if (op2 == 0) // 나누기 0 예외 처리
printf("DivideByZeroException\n");
push(&node, op1 / op2);
break;
}
}
token = cstrtok(NULL, delim);
}
return pop(&node);
}
int main(void)
{
int n = 0; // 반올림 자리
double result = 0.0; // 계산 결과
char *exp; // 입력
char postfix[MAX_SIZE] = {'\0'};
exp = (char *)malloc(sizeof(char) * 100);
printf("계산식을 입력한 후 Enter를 눌러주세요!\n");
scanf("%s", exp);
toPostfix(exp, postfix);
printf("\nPostfix: %s\n", postfix);
printf("몇 번째 자리에서 반올림하시겠습니까? >>>");
scanf("%d", &n);
result = calculate(postfix);
printf("계산한 결과: \t%.3f\n", cround(result, n));
return 0;
}
References:
https://www.tcpschool.com/c/c_struct_intro
'C' 카테고리의 다른 글
| 왜 C언어를 사용하는가 (0) | 2024.07.01 |
|---|
'C' Related Articles
more
