티스토리 뷰
C언어를 이용한 자료구조 실습입니다.
사용자로부터 식은 입력 받아 스택을 사용하여 후위 식으로 변환한 다음 계산하여 출력하는 문제입니다.
추가사항에 있는 거듭제곱, 오류정정, 두 자리 수(이상) 사용 가능을 구현하였습니다.
I. 문제
사용자로부터 수식을 입력받고, 이를 후위 식으로 변환하고, 후위 식을 평가하여 그 결과 값을 출력하는 계산기 프로그램을 작성하고 테스트하라.
[계산기 특징]
- 입력: 3*(2+8)/5
- 출력: 3*(2+8)/5 = 6
[수식의 특징]
- 다양한 괄호 포함 가능
- 공백 포함 가능
- 사칙 연산자 포함
[프로그램 작성 지침]
다음 함수들을 작성하고, 이용하라.
- get_exp(exp) // 사용자로부터 식을 읽어들여서 반환
- postfix(iexp, pexp) // 중위식 iexp를 후위식 pexp로 변환하여 반환
- eval(pexp) // 후위식 pexp를 평가하고, 그 결과값을 반환
- get_token(exp) // 호출시마다 수식 exp로부터 다음번째 토큰을 식별하여 반환
[추가 고려 사항]
- 피연산자 수치를 2자리 이상 허용
- 거듭제곱 연산자 ‘^’ 추가 (2^3 = 8)
- 오류 검사 기능 (잘못 표현된 수식에 대한 오류 메시지 출력)
- GUI(graphical user interface) 기능 제공
II. 구현
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX_STACK_SIZE 100 // 스택 최대 크기
typedef struct {
int data[MAX_STACK_SIZE];
int top;
}Stacktype;
void init_stack(Stacktype* s) {
s->top = -1;
}
int is_empty(Stacktype* s) {
return s->top == -1;
}
int is_full(Stacktype* s) {
return (s->top == (MAX_STACK_SIZE - 1));
}
void push(Stacktype* s, int item) {
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
s->data[++(s->top)] = item;
}
int pop(Stacktype* s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[s->top--];
}
int peek(Stacktype* s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[s->top];
}
/* -----스택기본골격---- */
// 연산자 우선순위 반환
int prec(char op)
{
switch (op) {
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
}return -1;
}
// 수식을 입력받아 반환
void get_exp(char* exp)
{
printf("수식을 입력해주세요: ");
scanf("%[^\n]s", exp);
}
// 수식에서 한 글자씩(토큰) 반환
char get_token(char* exp, int i)
{
return exp[i];
}
// 스택을 이용하여 괄호 오류 확인
int check_exp1(char* exp)
{
char token, open_token;
int i = 0;
Stacktype s;
init_stack(&s);
for (int i = 0; i < strlen(exp); i++)
{
token = exp[i];
switch (token)
{
// 토큰이 열린 괄호일때는 push
case '(': case'[':case '{':
push(&s, token);
break;
// 닫힌 괄호 라면
case ')': case']':case '}':
// 스택이 비어있을 때 -> 오류
if (is_empty(&s)) {
return 0;
}
else { // pop한 괄호와 짝이 안맞을 때 -> 오류
open_token = pop(&s);
if ((open_token == '(' && token != ')') ||
(open_token == '[' && token != ']') ||
(open_token == '{' && token != '}'))
return 0;
break;
}
// 괄호종류가 아니라면 패스
default:
break;
}
}
// 짝이 없는 괄호가 스택에 남아있을 때 -> 오류
if (!is_empty(&s))
return 0;
return 1;
}
// 사용할 수 없는 문자가 포함 되어있는지 확인
int check_exp2(char* exp)
{
char token;
for (int i = 0; i < strlen(exp); i++)
{
token = exp[i];
// 숫자가 아니라면 -> 오류
if (!(token >= '0' && token <= '9'))
// 연산자가 아니라면 -> 오류
if (!(token == '+' || token == '-' || token == '*' || token == '/' || token == '^'))
// 괄호, 공백이 아니라면 -> 오류
if (!(token == '(' || token == ')' || token == '[' ||
token == ']' || token == '{' || token == '}' || token == ' '))
return 0;
}
}
// 중위식 -> 후위식 변환
void postfix(char* iexp, char* pexp)
{
int j = 0;
char token, top_op;
//스택생성
Stacktype s;
init_stack(&s);
for (int i = 0; i < strlen(iexp); i++) {
// 수식에서 토큰을 하나 가져와서
token = get_token(iexp, i);
switch (token)
{
case '+': case '-': case'*':case '/': case '^': //연산자(+,-,*,/,^)이라면
/* 스택이 비어있지 않고 스택에 들어있던 연산자의 우선순위가
토큰의 우선순위보다 크거나 같을때 */
while (!is_empty(&s) && (prec(token) <= prec(peek(&s))))
{
// 공백삽입
pexp[j++] = ' ';
// 연산자 삽입
pexp[j++] = pop(&s);
}
// 공백 삽입
pexp[j++] = ' ';
// 연산자 push
push(&s, token);
break;
// 열린괄호일 때, 삽입
case '(': case '{': case '[':
push(&s, token);
break;
// 닫힌 괄호일 때, 짝인 열린괄호를 만날때까지 삽입
case ')':
top_op = pop(&s);
while (top_op != '('){
// 공백삽입,괄호 안에 있는 연산자 삽입
pexp[j++] = ' ';
pexp[j++] = top_op;
top_op = pop(&s);
}break;
// 닫힌괄호일 때, 짝인 열린괄호를 만날때까지 삽입
case '}':
top_op = pop(&s);
while (top_op != '{'){
pexp[j++] = ' ';
pexp[j++] = top_op;
top_op = pop(&s);
}break;
// 닫힌괄호일 때, 짝인 열린괄호를 만날때까지 삽입
case ']':
top_op = pop(&s);
while (top_op != '['){
pexp[j++] = ' ';
pexp[j++] = top_op;
top_op = pop(&s);
}break;
// 공백일 때, 아무것도 하지 않음
case ' ':
break;
// 피연산자일 때 삽입
default:
pexp[j++] = token;
break;
}
}
//나머지 스택에 남아있던 연산자들 삽입
while (!is_empty(&s)) {
pexp[j++] = ' ';
pexp[j++] = pop(&s);
}
}
// 후위식 계산
int eval(char* pexp)
{
int first, second, k = 0;
char token;
char num[100] = { "" }; // 두 자리 이상의 수를 받기 위해 배열로 선언
// 사용할 스택 생성
Stacktype s;
init_stack(&s);
for (int i = 0; i < strlen(pexp); i++){
// 후위식에서 토큰을 가져옴
token = get_token(pexp, i);
// 피연산자일 경우 num에 삽입
if (token >= '0' && token <= '9')
num[k++] = token;
// 피연산자가 아닐 경우
else {
// 빈칸이고 num이 비어있지 않을 때
if (token == ' ' && num[0] != ' ') {
// num문자열을 숫자로 바꾸어 스택에 삽입
push(&s, atoi(num));
// num빈칸으로 다시 초기화, k=0으로 다시 초기화
for (int j = 0; j < strlen(num); j++)
num[j] = ' ';
k = 0;
}
// 연산자(+,-,*,/,^)이라면
else if (token == '+' || token == '-' || token == '*' || token == '/' || token == '^')
{
// 스택에 맨위,그다음 숫자를 pop한 뒤 변수에 저장
second = pop(&s);
first = pop(&s);
// 연산자에 따라 다른 연산을 한 뒤, push
switch (token){
case '+': push(&s, first + second); break;
case '-': push(&s, first - second); break;
case '*': push(&s, first * second); break;
case '/': push(&s, first / second); break;
case '^': push(&s, pow(first, second)); break;
}
}
}
}
// 스택에 남아있는 값을 반환
return pop(&s);
}
int main(void) {
// 중위식, 후위식선언
char iexp[100] = { "" };
char pexp[100] = { "" };
// 중위식 입력받기
get_exp(iexp);
if (check_exp1(iexp) == 0)
printf("!!괄호 오류!!\n");
else if (check_exp2(iexp) == 0)
printf("!!사용할 수 없는 문자가 포함되어 있습니다!!\n");
//두 오류가 없다면 진행
else {
// 중위식->후위식 함수
postfix(iexp, pexp);
// 결과 출력
printf("후위수식변환: ");
puts(pexp);
printf("결과값: %d\n", eval(pexp));
}
return 0;
}
III. 결과
+ 과제를 할 당시 추가기능을 구현하기 위해 꽤나 고민을 했던 기억이 납니다. 특히 2자리 수 계산 기능을 구현하는데에 어려움이 있었는데, 저는 후위식으로 변환을 할 때 피연산자를 제외한 토큰들을 삽입한 이후에 띄어쓰기를 하나씩 넣어주는 것으로 이를 해결하였습니다. 때문에 postfix 함수에서 ' '를 pexp에 추가하는 것을 볼 수 있죠. 정말 간단한 방법인데도 떠올리는데에 어려움이 많았네요. 문제에서는 2자리수 계산이 가능하라고 나왔지만 이 방법을 사용해서 2자리 수가 넘어가더라도 계산이 잘 되도록 구현할 수 있었습니다.
감사합니다.
공부한 내용을 복습/기록하기 위해 작성한 글이므로 내용에 오류가 있을 수 있습니다.
'C | 자료구조' 카테고리의 다른 글
| [C/자료구조] 덱 구현하기 (feat. 회문) (0) | 2023.10.29 |
|---|---|
| [C/자료구조] 스택 2개로 큐 구현하기 (0) | 2023.10.29 |
| [C/자료구조] 연결리스트 생성 구현하기 (0) | 2023.10.28 |
| [C/자료구조] 희소행렬의 표현과 덧셈함수 구현하기 (0) | 2023.10.28 |
| [C/자료구조] 다항식의 계산 (1) | 2023.10.28 |
댓글