Stack - 후위표기법 -1(계산)

구현 된 후위표기법으로 이제 계산을 해보자

 

이전글에서 변환한 후위표현 식은 다음과 같다.

 

"51 8 3 4 * 4 - / - 20 -"

 

 

계산 방법은 다음과 같다.

 

1.  앞에서부터 SCAN 하면서 연산기호를 찾는다.

 

 

2. 연산 기호 앞에 2개의 숫자를 기호에 맞게 계산한다.

 

3. 다시 Stack에 집어 넣는다.

 

 

 

4. 연산 기호가 없을 때 까지 계산한다.

 

함수는 다음과 같다.

 

int Postfix_Calc(int *char_arr, int length)
{
	int index;
	int result;

	int operator_0;
	int operator_1;

	Stack LStack, NStack;

	StackInit(&LStack);
	StackInit(&NStack);

	/* 배열의 index 크기를 구한다. */
	for (index = 0; char_arr[index] != 0; index++);

	/* 배열을 끝에서 부터 Stack 에 옮긴다 */
	while (index >= 0)
	{
		SPush(&LStack, char_arr[index--]);
	}

	/* 후위표현법으로 변경되어 저장된 Stack을 다음과 같이 처리한다..*/
	while (LStack.stack_ptr != 0)
	{
		/*일반 숫자라면  Stack에 PUSH 한다.*/
		if (SPeek(&LStack) != '*' && SPeek(&LStack) != '+'
				&& SPeek(&LStack) != '-' && SPeek(&LStack) != '/')
		{
			SPush(&NStack, SPop(&LStack));
		}
		else
		{
			/*연산 부호라면 다음과 같이 계산한다.*/
			switch (SPop(&LStack))
			{
			case '*':
				operator_0 = SPop(&NStack);
				operator_1 = SPop(&NStack);
				result = operator_1 * operator_0;
				SPush(&NStack, result);
				break;

			case '/':
				operator_0 = SPop(&NStack);
				operator_1 = SPop(&NStack);
				result = operator_1 / operator_0;
				SPush(&NStack, result);
				break;

			case '+':
				operator_0 = SPop(&NStack);
				operator_1 = SPop(&NStack);
				result = operator_1 + operator_0;
				SPush(&NStack, result);
				break;

			case '-':
				operator_0 = SPop(&NStack);
				operator_1 = SPop(&NStack);
				result = operator_1 - operator_0;
				SPush(&NStack, result);
				break;

			}
		}

	}
	/*Stack Pointer가 1개 남았으면 마지막 결과 값이므로 그 값을 Return 한다. */
	return SPop(&NStack);
}

 

함수 시작을 보면 Stack을 2개 만든다 

 

1개는 식을 저장할 Stack(LStack)이고 다른 한개는 연산기호를 빼기 위해 빼놓은 숫자들을 저장하기 위한 Stack(NStack)이다.

 

연산기호가 나오면 연산기호는 제거하고 빼놓은 NStack에서 2개를 빼서 연산기호에 맞게 계산 후 다시 NStack에 저장한다.

 

Stack Pointer가 0이 될 때까지 계속 한다.

 

 Main은 다음과 같이 하였다.

 

Main 함수

int main(void)
{
	int length = 0;
	memset(normal_array, 0, ARRAY_SIZE);

	char *calc_equal =
			{"51-8/(3*4-4)-20"};
	length = STRtoINT(calc_equal, normal_array);

	Postfix_func(normal_array, length);

	printf("calc result is: %d \r\n", Postfix_Calc(normal_array, length));

}

 

 

실행 결과