#include<stdio.h>
#include<stdlib.h>//문자열을 정수형으로 변환함
#include<math.h>//x값보다 가장 작은 정수값을 구함
#include<malloc.h>//메모리할당
#include<conio.h>//현재텍스트 윈도우의 내용을 지운후 커서를 왼쪽위로 이동시킴
#include<dos.h>
#include<ctype.h>//문자를 분류하는 함수들을 정의
#define MAX 100 //배열의 최대개수를 지정
#define MAX_ROW 100 //화면의 최대 행의 수
#define MAX_COL 100 //화면의 최대 열의 수
typedef struct s_item
{
char value;
struct s_item *back;
}//구조체 s_item
STACK; /*스택을 구성하는 노드는
(데이타, 그 전 노드를 가르키는 포인터)로 구성*/
STACK *top ; //스택의 최상위를 가르키는 포인터
void make_stack(void);
void delete_stack(void); //스택을 malloc와 free를 사용하여 생성,소멸시킴
int create_to_stack(int push); //노드를 하나 더 생성
int delete_to_stack(void); //노드를 지움(free사용)
int check_top_stack(void); //스택의 꼭대기에 있는 값을 체크
int check_empty_stack(void); //스택이 비었는지 체크
void in_to_post(char *before,char *after);
//intofix형태의 수식을 postfix형식으로 고치를 함수
int calculator(char *ques);
//after에 있는 수식을 계산하여 그 값을 리턴
int operator01(int opr1); //operator01값 부여
int operator02(int opr2); //operator02값 부여
void main(void)
{
char infix[MAX]; //처음에 입력받은 수식을 넣음
char postfix[MAX]; //후에 변환된 수식을 넣음
int result; //결과값을 넣어둠
printf("\n");
printf("컴퓨터정보학과 2006270181 이재정\n");
printf("중위 표기법에서 후위 표기법으로 변환 후 계산하기!!!\n\n");
printf("중위 표기법으로 입력하시오 : ");
scanf("%s",infix); //입력받는 수식을 문자열로 받음
in_to_post(infix,postfix);//함수 in_to_post를 호출함
printf("후위 표기법으로 계산한 값 : %s\n",postfix);
in_to_post(infix,postfix);
result = calculator(postfix);//함수 calculator에서 계산된 값을 가져옴
printf("결과 값 : %d\n\n끝\n",result);//출력
}
//스택 형성
void make_stack(void)
{
top = (STACK *)malloc(sizeof(STACK));
//동적 메모리 할당
top->value = -1;
top->back = NULL;
}
//스택 삭제: free를 사용하여 메모리에 반환
void delete_stack(void)
{
free(top);//동적 메모리 할당 취소
}
//스택 추가
int create_to_stack(int push_value)
{
STACK *addptr;
addptr = (STACK *)malloc(sizeof(STACK));
if(addptr == NULL)
{
printf(" E R R O R \n");
exit(1);
}
addptr->value = push_value;
addptr->back = top;
top = addptr;
return push_value;
}
//스택에서 값을 catch
int delete_to_stack(void)
{
int pop_value;
int delptr;
if(top->back ==NULL)
{
printf(" E R R O R \n");
exit(1);
}
delptr = top;
pop_value = top->value;
top = top->back;
free(delptr);
return pop_value;
}
//스택의 꼭대기에 있는 값을 리턴해주거나 비었으면 -1을 리턴
int check_top_stack(void)
{
if(top->back == NULL) return -1;
else return top->value;
}
//스택이 비었으면 참값을 그렇지 않으면 거짓값을 리턴해준다.
int check_stack_empty(void)
{
return (top->back == NULL);
}
//각각의 연산자들에 operator01값을 넣어줌(계산에 쓰이는 연산자)
int operator01(int opr1)
{
switch(opr1)
{
case '^':return 3;
case '*':return 2;
case '/':return 2;
case '+':return 1;
case '-':return 1;
}
return 0;
}
//각각의 연산자들에 operator02값을 넣어줌(계산에 쓰이는 연산자)
int operator02(int opr2)
{
switch(opr2)
{
case '^':return 4;
case '*':return 2;
case '/':return 2;
case '+':return 1;
case '-':return 1;
}
return 0;
}
//infix -> postfix 형식으로 바꾸어주는 함수
void in_to_post(char *before, char *after)
{
make_stack(); //default노드를 생성
while(*before)
{
//입력된 문자열의 끝에 도달할 때까지 검사
switch(*before)
{
//입력된 문자열을 하나 하나 검사
case '\0': while (!check_stack_empty())
{
*after++ = delete_to_stack();
*after++ = ' ';
}
*after = '\0';
break;
case ' ':before++;
break;
//빈칸이면 건너 뛴다.
case '(':create_to_stack(*before);
before++;
break;
//'('면 그냥 스택에 push 한다.
case ')':while(check_top_stack()!='(')/*if ) -> to see ( -> loop */
{
*after++ = delete_to_stack();
*after++ = ' ';
}
delete_to_stack();
before++;
break;
//')' 면 '('를 만날 때 까지 pop 한다.
case '+':
case '-':
case '*':
case '/':
//스택에 있는 연산자의 operator01과 들어오는 연산자의 operator02를 비교
case'^': while(operator01(check_top_stack()) >= operator02(*before))
{
*after++ = delete_to_stack();
*after++ = ' ';
}
//결과가 크거나 값으면 POP한다.
create_to_stack(*before);
//그렇지 않으면 PUSH한다.
before++;
break;
default: //operand 인 경우
// 1자리 이상의 숫자가 들어 올 수 있으므로
while(*before >= '0' && *before <= '9')
*after++ = *before++;
*after++ = ' ';
}
}
//문자열의 끝이므로, 스택에 남아 있는 값들을 pop한다.
while(!check_stack_empty())
{
*after++ = delete_to_stack();
*after++ = ' ';
}
after--;
*after = 0;
}
//수식을 연산함
int calculator(char *ques)
{
int oper1;
int oper2;
int operand;
make_stack(); //operand의 임시 대피 장소
//수식의 끝을 만날 때까지 검사
while(*ques)
{
switch(*ques)
{
case ' ':ques++;
break;
case '+': // +이면 두 번 pop하여 더한다.
oper1 = delete_to_stack();
oper2 = delete_to_stack();
create_to_stack(oper1 + oper2);
ques++;
break;
case '*': // *이면 두 번 pop하여 곱한다.
oper1 = delete_to_stack();
oper2 = delete_to_stack();
create_to_stack(oper1 * oper2);
ques++;
break;
case '-': // -이면 후에 pop한 값에서 처음에 pop한 값을 뺀다.
oper1 = delete_to_stack();
oper2 = delete_to_stack();
create_to_stack(oper2 - oper1);
ques++;
break;
case '/': // '/'면 후에 pop한 값에서 처음에 pop한 값을 나눈다.
oper1 = delete_to_stack();
oper2 = delete_to_stack();
create_to_stack(oper2/oper1);
ques++;
break;
case '^': // ^면 후에 pop한 값을 처음에 pop한 값으로 pow한다.
oper1 = delete_to_stack();
oper2 = delete_to_stack();
create_to_stack(pow(oper2,oper1));
ques++;
break;
default: // 현재 숫자가 문자로 인식되고 있으므로
//char -> int형으로 바꿔주는 작업이 필요.
operand = 0;
do{
operand = operand*10 + *ques - '0';
ques++;
}while(*ques >= '0' && *ques <= '9');
create_to_stack(operand);
break;
}
}
// 그 결과 값을 리턴해준다.
return delete_to_stack();
}
// 자료구조 과목에서 후달리면 나중에 알고리즘 과목가서 개후달립니다.
// 자료구조는 100% 마스터 해주는 센스
