스택구조_후위표기식_수식 계산하기(괄호 없는 수식) [1/3]

[구현 목표]

• 수식 내 우선순위에 따른 계산 결과 도출
• ex) "2 + ((35+65) / 25) * 7" 과 같은 형태의 수식 계산 (엑셀과 비슷)

강의 보기 전에 미리 해보고 있는데 생각보다 엄청 복잡하네요.. 공부 하면서 가장 많이 느끼는 점은 간단해보이는 프로그램들이 실제로는 간단하지 않다는거.. 존경해요 MS..

 

---

 

괄호까지 한번에 해결하려고 했는데 제 머리로는 답이 안나오네요. 일단 괄호가 없는 식을 계산하는 함수를 만들고, 괄호가 나오면 함수를 통해 괄호가 없는 것처럼 따로따로 계산하는 방식을 사용하기로 했습니다.

​

[ main() ]

• 입력받을 수식을 저장하는 공간, 후위표기식으로 변환 저장할 공간, 결과값 공간 생성

#include <stdio.h>
#include <string.h>
#include <ctype.h>

void postfix(char* form, char* calc);
int calculation(char* calc);

int main()
{
	char form[] = "10+21*15-10/2*3";		// 후위표기식 : 10 21 15 * 10 2 / 3 * - +
	char calc[30] = "";						// 후위표현식 저장 공간
	int result;								// 결과값 저장
	
	postfix(form, calc);
	result = calculation(calc);
	printf("%s\n", calc);
	printf("%d\n", result);
}

 

---

 

[ void postfix() - 후위표기식으로 변환]

• 후위표기식의 공식만 이해하면 변환 규칙에 대한 이해 가능
• while문 마지막에 ++i 붙이는게 귀찮아서 그냥 -1부터 시작시킴
• 타입 변환을 바로 하고 싶다면 구조체를 이용해도 더 복잡해져서 그냥 먼저 string으로 저장
• oper(연산자 저장)의 순서만 유의하면 크게 어려운 점은 없는 듯​

※ Point
배열을 초기화해주지 않을 경우 크게 문제는 없지만 디버깅할 때 보기가 불편해질 수도 있기 때문에 생성과 동시에 초기화를 해주는게 깔끔함

 

/* infix → postfix 변환 */
/* parameter = 원본 문자열, 변환해서 저장한 문자열 */
/* return = void */
void postfix(char* form, char* calc)
{
	char oper[20] = "";  // 연산기호 저장 (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';
}

 

---

 

[후위표기식 계산]

• 마찬가지로 계산 순서인 result[w]의 순서만 유의하면 됨
• 수식 연산에서 숫자변환은 atoi보다 -'0'을 이용하는게 훨씬 깔끔한 듯

/* postfix 실제 계산 */
/* parameter = 후위표기식으로 변환된 문자열 */
/* result = 정상 : 계산, 비정상 : -1 */
int calculation(char* calc)
{
	int result[10] = { 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;
		}
	}