Stack - 후위표기법 -1(변환)

C에서 후위표기법으로 바꿔 보자

 

공식을 String을 쓰고 쓴 String을 INT로 바꾼다.

 

바꾸는 함수는 다음과 같다.

 

STRtoINT함수 

/* ASCII 값을 INT형으로 변경한다. */
int STRtoINT(char *char_arr, int *local_arr)
{
	int num = 0;
	int arr = 0;
	int int_len = 0;

	while (*char_arr != '\0')
	{
		if (*char_arr > '0' && *char_arr <= '9')
		{
			num = strtoul(char_arr, &char_arr, 10);

			local_arr[arr++] = num;

			int_len++;
		}
		else
		{
			local_arr[arr++] = (int) *char_arr;
			char_arr += 1;

			int_len++;
		}

	}

	return int_len;
}

 

 

 

후위표기법으로 바꾸기 위해서는 다음과 같은 조건을 만족하면 된다.

 

1. 숫자가 나오면 그냥 배열에 집어 넣는다.

 

2. 연산부호가 나오면 연산 스택에 집어넣는다

 

다만, 스택에 넣을때는 다음의 조건을 만족해야 한다.

 

조건문 1. 넣을려는 연산 부호는 스택에 쌓여 있는 부호 보다 우선순위가 클때만 스택에 PUSH 한다.

 

조건문 2. 스택에 쌓여 있는 부호의 우선순위가 크거나 같으면 POP을 하여 배열에 집어놓고 스택에 PUSH 한다.

언제까지? 조건문1이 만족할때 까지 

 

조건문 3. 괄호는 연산 순위에 상관없이 연산 Stack에 PUSH 한다. 다만 닫는 괄호가 나오면

여는 괄호가 나올 때 까지 스택에 있는 부호들을 POP 하여 배열에 집어 넣는다.

 

3. 연산 순위는 다음과 같다. (숫자가 높을수록 높은순위)

곱하기, 나누기 기호 : 5

더하기, 빼기 기호: 3

괄호 기호: 1

 

4. 수식에서 시작하는 순서는 왼쪽에서 오른족으로 진행한다.

-끝-

 

 

ex) "51-8/(3*4-4)-20"

 

1. 51은 일반 숫자이므로 배열에 넣는다.

 

2. -는 연산기호이므로 연산 스택에 넣는다.

 

3. 8 역시 일반 숫자이므로 배열에 넣는다.

 

4. 나누기 기호는 빼기 기호보다 우선순위가 높으므로 연산 스택에 쌓는다. 

 

 

5. 여는 괄호가 나오면 순위에 상관 없이 쌓는다.

 

6. 3은 배열에 다시 집어 넣고 곱하기는 연산 스택에 넣는다. 이때 괄호의 순위는 가장 낮으므로

더하기는 그대로 연산 스택에 쌓인다.

 

7. 빼기 기호를 연산 스택에 PUSH 할려고 보니  곱하기는 우선순위가 높다 따라서 곱하기는 POP 하여 배열에 들어간 다음 PUSH 된다. (기호가 더있으면 계속 검사한다)

 

8. 4를 배열에 넣고 닫는 기호가 나왔으므로 여는 기호가 나올 때 까지 연산을 POP 하여 배열에 넣는다.

 

 

9. 빼는 기호를 넣을려 보니 쌓여 있는 나누기 기호와 빼기 기호는 우선순위가 크거나 같으므로 배열에 집어 넣는다. 

 

 10.  빼기기호를 연산 스택에 넣는다. 마지막 20을 배열에 넣는다. 그리고 더이상 수식이 없으므로 연산 스택을 모두 빼서 배열에 넣는다.

 

 

 

 

 

코드는 다음과 같다.

 

연산 순위 Return 함수

 

/* 연산부호의 우선순위를 Return 하는 함수. */
int calc_op_check(int num)
{
	switch (num)
	{
	case '(':
	case ')':
		return 1;

	case '+':
	case '-':
		return 3;

	case '*':
	case '/':
		return 5;

	default:
		return num;

	}
}

 

후위표기법으로 변환 함수

/* 후위표현법으로 변경한다. */
int* Postfix_func(int *char_arr, int len)
{
	Stack Calc_Stack;
	int calc_array[ARRAY_SIZE];
	int index = 0;
	int arr = 0;
	int calc_len = 0;

	StackInit(&Calc_Stack);
	memset(calc_array, 0, ARRAY_SIZE);

	calc_len = len;

	while (len--)
	{
		/* 배열 값이 그냥 숫자 라면 */
		if (calc_op_check(char_arr[arr]) == char_arr[arr])
		{
			/* 그냥 ARRAY에 집어 넣는다. */
			calc_array[index++] = char_arr[arr];
			/* INDEX를 증가시킨다. */
			arr++;

		}
		/* 연산 부호이고 현재 연산 스택에 저장된 값이 없으면  */
		else if (Calc_Stack.stack_ptr == -1)
		{
			SPush(&Calc_Stack, char_arr[arr]);
			arr++;
		}
		else
		{
			/* Stack에 들어있는 연산부호 순위가 들어올 우선순위의 연산부호 순위보다 높거나 같으면
			 * POP하여 배열에 집어넣는다 (자기보다 낮은 우선순위 연산부호가 나오거나 바닥일 때 까지!!)  */
			while (calc_op_check(SPeek(&Calc_Stack))
					>= calc_op_check(char_arr[arr])
					&& calc_op_check(char_arr[arr]) != 1)
			{
				/*연산 스택에서 제거 후 일반 배열에 넣는다. */
				calc_array[index++] = SPop(&Calc_Stack);
			}

			/*  연산 스택에 집어 넣는다.*/
			SPush(&Calc_Stack, char_arr[arr]);

			/*집어 넣는 연산자가 닫는 괄호라면 */
			if (char_arr[arr] == ')')
			{
				/*제거 후 */
				SPop(&Calc_Stack);

				/* 여는 괄호가 나올 때 까지 연산자 스택에 있는 값들을 배열에 넣는다.*/
				while (SPeek(&Calc_Stack) != '(')
				{
					calc_array[index++] = SPop(&Calc_Stack);

				}

				/* 여는 괄호 제거 */
				SPop(&Calc_Stack);

				/*여는 괄호를 가리키고 있으므로 index +1을 한다.*/
				arr++;
			}
			else
			{
				/*일반 연산 기호이면 +1을 한다 여기서 하는 이유는  괄호 확인 후 처리 하기 위해*/
				arr++;
			}

		}

	}

   /*연산 스택의 나머지 기호들은 ARRAY에 집어 넣는다. */
	while (Calc_Stack.stack_ptr != -1)
	{
		calc_array[index++] = SPop(&Calc_Stack);
	}

	return (int*) memcpy(char_arr, calc_array, calc_len * (sizeof(int)));

}

 

 

※ 계산코드 짜면서 확인되었는데  연산기호는 40~47로 인식해서 이 숫자가 수식에 들어가면 잘못된 값이 나온다.

스터디를 위해 짠 코드라 수정하지 않고 그냥 올렸다.

 

코드 역시 정리하지 않고 주석으로 대체 하였다.