스택구조_후위표기식_수식 계산하기(괄호 포함 수식) [2/3]

괄호를 어떻게 해결할지 한참 고민했네요.

"괄호가 시작되면 별도의 수식으로 생각한다."

라는 점을 두고 한참 고민하다 답을 찾긴 했습니다. 맞는진 모르겠지만..ㅎㅎ

​

기본 개념도는 아래와 같습니다. 괄호가 시작될 때마다 새로운 배열로 만들어주고, 괄호가 닫히면 괄호안의 값을 계산해서 앞 수식의 뒤에 붙여주는 방식으로 괄호가 없는 최종 수식을 만들어내면 되네요. 괄호만 잘 골라내주면 어제 만든 계산 수식을 이용해 간단히 짤 수 있었습니다.

 

 

---

 

[ main() ]

• 수식이 길어져서 소스파일을 나눔

#include "Header.h"

int main()
{
	/* 중위표기식 원본 문자열*/
	char form[] = "10+21*(2*(15-10)/2)-3";

	int result = calculation_all(form);
	printf("%d", result);

	return 0;
}

 

---

 

[ Header.h ]

• plagma once 대신 표준 코드로 구성 (그냥 해봄..)

#ifndef HEADER_H	
#define HEADER_H

#include <stdio.h>
int calculation_all(char* form);

#endif

 

---

 

[ void postfix() - 제공된 중위표기식 문자열을 후위표기식으로 변경 ]

• 이전 글과 동일한 로직

/* infix → postfix 변환 */
/* parameter = 중위표기식 문자열, 후위표기식 변환해서 저장할 주소 */
/* return = void */
void postfix(char* form, char* calc)
{
	char oper[10] = "";  // 연산기호 저장 (operator)

	int c = 0;  // calc 저장 순서
	int w = 0;  // operator 저장 순서

	int i = -1;
	while (form[++i] != '\0')
	{
		/* 숫자는 calc에 삽입 */
		if (form[i] > 47 && form[i] < 58)
		{
			calc[c++] = form[i];
			continue;
		}
		calc[c++] = ' ';  // 하나의 숫자가 끝나면 반드시 공백을 둬 구분


		/* 첫 연산기호는 무조건 oper에 저장 */
		if (w == 0)
			oper[w++] = form[i];

		/* '+', '*' 형태라면 그냥 저장해둠 */
		else if ((form[i] == '*' || form[i] == '/') &&
			(oper[w - 1] == '+' || oper[w - 1] == '-'))
			oper[w++] = form[i];

		/* '*', '/' 형태라면 이전 연산자를 이동시켜주고 그 자리에 저장 */
		else if ((form[i] == '*' || form[i] == '/') &&
			(oper[w - 1] == '*' || oper[w - 1] == '/'))
		{
			calc[c++] = oper[w - 1];
			oper[w - 1] = form[i];
		}

		/* '+,-'가 나오면 oper에 저장된 모든 연산자를 역순으로 이동하고 저장 */
		else if (form[i] == '+' || form[i] == '-')
		{
			for (int i = w - 1; i >= 0; i--)
			{
				calc[c++] = oper[i];
				w--;
			}
			oper[w++] = form[i];
		}
	}

	/* 수식의 마지막이 되어 반복문을 빠져나오면, 남은 연산자를 역순으로 붙여줌 */
	if (w > 0)
	{
		calc[c++] = ' ';
		for (int i = w - 1; i >= 0; --i)
			calc[c++] = oper[i];
	}

	/* 후위표기식 문자열 마지막 처리*/
	calc[c] = '\0';
}


/* 배열 생성 */
/* parameter : void */
/* return : 메모리 주소 */
char* create_str()
{
	// char str[MAX] 배열 생성
	char* temp;
	if((temp = (char*)malloc(sizeof(char) * MAX)) == NULL)
		return NULL;
	// 미리 '\0'값으로 초기화
	for (int i = 0; i < MAX; ++i)
		temp[i] = '\0';
	return temp;
}

 

---

 

[ int calculation_one - 후위표기식으로 받은 문자열을 계산해서 결과값 리턴 ]

• 이전 글과 동일한 로직
• postfix() 함수를 안에 넣어서 중위표기식 문자열만 넣어주면 계산값을 리턴하도록 함

/* postfix 실제 계산 */
/* parameter = 중위표기식 문자열 */
/* return = 정상 : 계산결과, 비정상 : -1 */
int calculation_one(char* form)
{
	char calc[MAX] = "";  // 후위표기식으로 변환해서 저장할 공간
	postfix(form, calc);  // 중위표기식 문자열을 후위표기식으로 변환해서 calc에 저장

	int result[MAX] = { 0 };  // 숫자 변환을 위해 0으로 초기화
	int w = 0;	// result 갯수(순서)

	int i = -1;
	while (calc[++i] != '\0')
	{
		/* 공백이 나오기 전까지 숫자로 변환해서 result에 저장 */
		if (!isspace(calc[i]) && calc[i] > 47 && calc[i] < 58)
		{
			result[w] = result[w] * 10 + (calc[i] - '0');
			continue;
		}

		/* 공백이 나오면 다음 숫자, result 다음칸으로 이동 */
		/* 숫자 뒤에는 무조건 공백이 나오도록 설계됨 */
		else if (isspace(calc[i]))
			w++;

		/* 공백이 아닌 연산자가 나오면 계산 수행 */
		else if (w > 1 && calc[i] == '*')
		{
			// w의 위치는 항상 마지막 숫자의 다음 칸
			// 실제 계산이 이뤄지면 w를 한칸 앞으로 당기고 초기화
			result[w - 2] *= result[w-- - 1];
			result[w] = 0;
		}

		else if (w > 1 && calc[i] == '/')
		{
			result[w - 2] /= result[w-- - 1];
			result[w] = 0;
		}

		else if (w > 1 && calc[i] == '+')
		{
			result[w - 2] += result[w-- - 1];
			result[w] = 0;
		}

		else if (w > 1 && calc[i] == '-')
		{
			result[w - 2] -= result[w-- - 1];
			result[w] = 0;
		}
	}

	/* 결과값은 무조건 1개가 남아 있어야 정상처리(연산기호가 하나도 없을 때는 w == 0) */
	if (w <= 1)
		return result[0];
	else return -1;
}

 

---

 

[ int calculation_all() - 괄호가 있는 중위표기식 문자열을 받아 처리하는 최종 함수 ]

• 열린괄호가 나올 때마다 신규 배열값 추가
• 닫힌괄호가 나오면 마지막 순서에 있는 값을 계산 후, 이전배열값에 추가

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX 40

void postfix(char* form, char* calc);  // main에는 불필요
char* create_str();  // main에는 불필요
int calculation_one(char* form);  // main에는 불필요

/* 괄호 있는 수식 전체 계산*/
/* parameter : 중위표기식 전체 수식 문자열 */
/* return : 정상 == 계산결과, 비정상 == exit */
int calculation_all(char* form)
{
	char* form_exch[MAX] = { NULL };  // 계산식 저장 공간
	form_exch[0] = create_str();  // 첫번째 공간 할당

	int result = 0;	// 최종 결과값 저장
	int f = 0;  // form_exch count
	int w = 0;  // form_exch[f][] count
	
	for (int i = 0; form[i] != '\0'; ++i)
	{
		/* 괄호가 나올때까지는 form_exch[f]의 string에 수식 저장 */
		if (form[i] != '(' && form[i] != ')')
		{
			form_exch[f][w++] = form[i];
			form_exch[f][w] = '\0'; // release 모드에서는 불필요
		}

		/* 열린괄호가 나오면 form_exch[f+1]을 새로 생성 */
		else if (form[i] == '(')
		{
			form_exch[++f] = create_str();
			w = 0;	// 새로운 fomr_exch[f]가 시작됐으므로 w를 초기화
		}
		
		/* 닫힌괄호가 나오면 form_exch[f] 값을 계산하여 form_exch[f-1]에 붙임 */
		else if (form[i] == ')')
		{
			// [f]의 계산된 값을 붙여넣을 [f-1][q]의 순서
			w = strlen(form_exch[f - 1]);
						
			// [f]의 계산결과를 [f-1]에 문자열로 붙여주기 (w값 한칸 이동시켜두기)
			sprintf_s(&form_exch[f - 1][w++], sizeof(int), 
						"%d", calculation_one(form_exch[f]));
			
			// 계산을 마친 [f]의 공간을 free해주고 f를 한칸 줄임
			free(form_exch[f]);
			form_exch[f--] = NULL;
		}
	}
	/* 수식이 끝났으면 최종 계산 수행 */
	result = calculation_one(form_exch[f]);
	return result;
}

 

---

 

엑셀 등에서 당연하게 사용하던 것들도 직접 짜보니 쉽지가 않네요..

다 풀었으니 이제 강의 들으러! 더 효율적인 방법이 있는지 확인해봐야곘네요.