중위표기법 후위표기법 변환 및 계산

무려 제가 작년에 제출한 과제입니다...✪ ω ✪

파일에서 읽어오는 과정이랑 지수계산때매 애먹었던 기억이 나네요...

 

-문제

다음의 조건 하에서 중위표기법(infix notation) 수식들을 파일로부터 입력 받아 각 중위 표기법 수식을 후위 표기법(postfix notation)으로 변환한 후, 변환된 수식의 값을 계산하는 프로그램을 작성하라.

 

(1) 중위 표기법 수식에는 괄호가 들어갈 수 있다.

(2) 중위 표기법 빛 후위표기법 수식은 세미콜론으로 끝낸다

=> 이를 통해 각 식의 종료를 판단할 수 있다.

(3) 피연산자(operand)는 하나의 숫자 문자로 된 상수이다.

=> 식을 한 글자씩 쪼개어 변환 및 연산을 진행한다.

(4) 연산자(operator)는 +,-,*,/,%,^로만 구성된다. (단, 모든 연산은 정수형 연산이며, %는 나머지 연산, ^는 지수연산을 의미한다.)

=> ^연산자는 우결합 연산자이므로 스택 내부 우선순위(ISP)와 스택 진입 우선순위(ICP)를 구분한다. (우결합 연산자의 ICP를 ISP보다 높이고 왼쪽 괄호는 오른쪽 괄호가 나올 때까지 스택에 머물도록 하기 위해 왼쪽괄호의 ICP를 매우 높여주고 ISP를 매우 낮춘다.)

(5) 연산자 스택은 반드시 배열을 사용하여 구현하고, 피연산자 스택은 연결리스트를 사용하여 구현한다.

(6) 모든 수식은 문법적으로 맞다고 가정한다.

(7) 테스트 데이터는 사이버강의실 공지사항에 주어지는 파일 infix.txt 를 사용하되, 추가로 수식을 본인이 만들어서 테스트할 수 있다.

=> 파일을 한 줄씩 읽어온다. 파일의 가장 첫번째 줄은 수식의 개수로, int count에 저장한 후 다음 줄부터 한 줄씩 읽어 변환 및 계산을 진행한다.

 

(=> 이후 설명은 제가 추가한 부연설명입니다.)

 

-소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_STACK_SIZE 100
typedef char element; //데이터의 자료형(연산자스택)
typedef int element1; //데이터의 자료형(피연산자 스택)

//연산자 스택(배열)
element OperatorStack[MAX_STACK_SIZE];
int top = -1;

//연산자 스택 공백 검사 함수
int is_empty_tor() {
	return top == -1;
}

//연산자 스택 포화 검사 함수
int is_full_tor() {
	return top == (MAX_STACK_SIZE - 1);
}

//연산자 스택 push 함수(포화 상태시, 에러 메시지 출력 후 종료)
void push_tor(element item) {
	if (is_full_tor()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else OperatorStack[++top] = item;
}

//연산자 스택 pop 함수(공백 상태시, 에러 메시지 출력 후 종료)
element pop_tor() {
	if (is_empty_tor()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return OperatorStack[top--];
}

//연산자 스택 peek 함수(공백 상태시, 에러 메시지 출력 후 종료)
element peek_tor() {
	if (is_empty_tor()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return OperatorStack[top];
}

//피연산자 스택(연결리스트 이용하여 구현)
typedef struct OperandStack {
	element1 data;
	struct OperandStack* link;
}OperandStack;

typedef struct {
	OperandStack* top;
}LinkedStackType;

//피연산자 초기화 함수
void init_and(LinkedStackType* s) { 
	s->top = NULL;
}

//피연산자 공백 상태 검출 함수
int is_empty_and(LinkedStackType* s) {
	return(s->top == NULL);
}

//피연산자 포화 상태 검출 함수
int is_full(LinkedStackType* s) { 
	return 0;
}

//피연산자 push 함수
void push_and(LinkedStackType* s, element1 item) { 
	OperandStack* temp = (OperandStack*)malloc(sizeof(OperandStack));
	temp->data = item;
	temp->link = s->top;
	s->top = temp;
}

//피연산자 pop 함수(공백 상태시, 에러 메시지 출력 후 종료)
element1 pop_and(LinkedStackType* s) {
	if (is_empty_and(s)){
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		OperandStack* temp = s->top;
		int data = temp->data;
		s->top = s->top->link;
		free(temp);
		return data;
	}
}

//피연산자 peek 함수(공백 상태시, 에러메시지 출력 후 종료)
element1 peek_and(LinkedStackType* s) {
	if (is_empty_and(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		return s->top->data;
	}
}


//ICP 우선순위(스택에 들어올 때)
int icp(char op) {
	switch (op) {
	case '(':  return 20;
	case '+': case '-': return 12;
	case '*': case '/': case '%': return 13;
	case '^': return 15;
	}
}

//ISP 우선순위(이미 스택에 들어 있는 상태일 때)
int isp(char op) {
	switch (op) {
	case '(': return 0;
	case '#': return -1;
	case '+': case '-': return 12;
	case '*': case '/': case '%': return 13;
	case '^': return 14;
	}
}

//식을 한 문자씩 자르기 위한 함수
char get_Token(char exp[], int *i) {
	return exp[*i];
}

//숫자인지 확인하는 함수
int is_digit(char token) {
	return (token != '+' && token != '-' && token != '*' && token != '/' && token != '%' && token != '^'&&token!='('&&token!=')');
}

//중위표기법을 후위표기법으로 바꾸는 함수(exp : 파일에서 읽어온 중위표기법 식, str : 후위표기법으로 바꾼 식 저장)
void infix_to_postfix(char exp[], char str[]) {
	char token; //exp를 한 문자씩 끊어 읽기 위한 변수(문자)
	int k = 0; //str에 문자 저장하기 위한 변수(str의 인덱스)
	top = 0; //연산자 스택의 top 값을 0으로 설정(bottom을 #로 표기하므로)
	int index = 0; //exp를 한 문자씩 끊어 읽기 위한 변수(인덱스 값)
	OperatorStack[0] = '#'; //연산자 스택의 bottom을 #으로 표시

	for (token = get_Token(exp, &index); token != ';'; token = get_Token(exp, &(++index))) { //&index값을 증가시키며 exp를 한 글자씩 끊어 읽음(';'만날 때까지)
		if (is_digit(token)) // token이 숫자일 경우 바로 str에 추가
			str[k++] = token;
		else if (token == ')') { //token이 ')'일 경우, OperatorStack[top]이 '('가 나오기 전까지 pop해서 str에 추가
			while (OperatorStack[top] != '(') {
				str[k++] = pop_tor();
			}
			pop_tor(); //'('을 연산자 스택에서 pop 
		}
		else {
			while (isp(OperatorStack[top]) >= icp(token)) { //연산자 스택 top에 있는 것의 우선순위>=exp에서 읽어온 token 일 때 연산자 스택 pop하여 str에 추가
				str[k++] = pop_tor();
			}
			push_tor(token); //token의 우선순위가 연산자 스택의 top에 있는 것의 우선순위보다 클 때 token을 연산자 스택에 push 함
		}
	}
	while ((token=pop_tor())!='#') //';'을 만났을 경우, 식이 끝난 것이므로 연산자 스택 안에 남아있는 연산자들을 모두 pop하여 str에 추가
		str[k++] = token;

	str[k++] = ';'; //각 후위표기식의 끝을 구분하기 위해 끝에 ';'를 추가
}
//후위 표기 수식 계산 함수
int eval(char exp[]) {
	char token; //exp를 한 글자씩 읽어오기 위한 변수
	int index = 0; //exp를 한 글자씩 읽어오기 위한 변수2(인덱스값)
	int value; //char형태의 token을 숫자로 바꿔 저장할 변수(계산을 위해)
	int op1, op2; //계산을 위해 피연산자를 피연산자 스택에서 pop하여 저장할 변수
	LinkedStackType s_and; //피연산자 스택

	init_and(&s_and);//피연산자 스택 초기화

	for (token = get_Token(exp, &index); token != ';'; token = get_Token(exp, &(++index))) { //&index값을 증가시키며 exp를 한 글자씩 끊어 읽음(';'만날 때까지)
		if (is_digit(token)) {//피연산자의 경우 연결리스트에 push
			value = token - '0'; //int형으로 변환하기 위해 token-'0'
			push_and(&s_and, value);
		}
		else { //연산자의 경우 피연산자 pop
			op2 = pop_and(&s_and); //스택은 LIFO의 방식이므로 첫번째로 pop되는 연산자가 op2
			op1 = pop_and(&s_and);
			switch (token) { //연산 수행 후 스택(연결리스트 스택)에 저장
			case '+': push_and(&s_and, op1 + op2); break;
			case '-': push_and(&s_and, op1 - op2); break;
			case '*': push_and(&s_and, op1 * op2); break;
			case '/': push_and(&s_and, op1 / op2); break;
			case '^': push_and(&s_and, pow(op1,op2)); break;
			case '%': push_and(&s_and, op1 % op2); break;
			}
		}
	}
	return peek_and(&s_and); //peek함수를 이용하여 연산 결과를 return 함
}

//메인함수
int main(void) {
	char line[300]; //파일을 읽을 때 사용할 공간
	int i = 0; //for문에 사용될 변수
	int result; //연산 결과를 저장할 변수
	char ch='0';//식들을 한 글자씩 읽어오기 위한 변수('0'으로 초기화)
	int len;//식의 길이를 저장하기 위한 변수(for문의 조건식에 사용)

	FILE* file1 = fopen("infix.txt", "r");
	int count = (int)fgets(line, sizeof(line), file1); //파일 첫째 줄 담아올 변수(식의 개수)
	while (fgets(line, count, file1) != NULL) {
		char str[MAX_STACK_SIZE] = { '\0' }; //while문 돌 때마다 str을 '\0'로 초기화 해줌
		len = strlen(line);
		printf("infix notation = "); 

		for (i=0; i<len; i++) {//line을 한 글자씩 읽어온 후 출력(사이에 공백 삽입)
			ch = line[i];
			printf("%c ", ch);
		}
	
		printf("postfix notation = ");
		infix_to_postfix(line, str); //중위표기식을 후위표기식으로 변환

		len = strlen(str);
		for (i = 0; i < len; i++) { //str을 한 글자씩 읽어온 후 출력(사이에 공백 삽입)
			ch = str[i];
			printf("%c ", ch);
		}
		printf("\n");
		result = eval(str); //후위표기식을 계산
		printf("value = %d\n", result); //결과값 출력
		printf("\n");
	}

	fclose(file1); //파일 닫음

	return 0;
}

 

-결과

 

 

중위표기법

후위표기법

계산결과

순입니다.