열혈 자료구조 - 6-4. 스택을 활용한 계산기 프로그램 구현(2)

중위 표기법을 후기 표기법으로 변환하는 코드

- 연산자의 우선순위를 반환하는 함수

    -> 스택에 저장된 연산자를 비교하기 위함

    -> 값들은 연산자들끼리 대소가 비교될 수 있는 값만 가지면 됨 ( 꼭 5,3,1일 필요 없음 )

int GetOpPrec(char op)
{
	switch(op)
	{
	case '*':
	case '/':
		return 5;
	case '+':
	case '-':
		return 3;
	case '(':
		return 1;		// '(' 연산자는 스택의 가장 아래에 있어야 하기 때문
	}

	return -1;   // 등록되지 않은 연산자
}

- 두 연산자의 우선 순위 비교

int WhoPrecOp(char op1, char op2)
{
	int op1Prec = GetOpPrec(op1);		// 연산자의 우선순위를 구함
	int op2Prec = GetOpPrec(op2);

	if(op1Prec > op2Prec)
		return 1;
	else if(op1Prec < op2Prec)
		return -1;
	else
		return 0;
}

- 실제 변환 함수

void ConvToRPNExp(char exp[])
{
	Stack stack;
	int expLen = strlen(exp);
	char * convExp = (char*)malloc(expLen+1);		// 변경될 수식을 담을 char 배열

	int i, idx=0;
	char tok, popOp;
	
	memset(convExp, 0, sizeof(char)*expLen+1);		// 문자열 초기화
	StackInit(&stack);				// 연산자를 담을 스택 초기화

	for(i=0; i<expLen; i++)
	{
		tok = exp[i];
		if(isdigit(tok))
		{
			convExp[idx++] = tok;
		} // 숫자면 변경 수식으로 옮김
		else
		{
			switch(tok)
			{
			case '(':
				SPush(&stack, tok);	// 소괄호 열기면 바로 스택에 넣음
				break;

			case ')':		// 소괄호 닫기가 나왔을 때 스택의 것을 꺼내서 수식에 저장
				while(1)
				{
					popOp = SPop(&stack);
					if(popOp == '(')		// 열기가 나올때 까지 루프가 돔
						break;
					convExp[idx++] = popOp;
				}
				break;

			case '+': case '-': 
			case '*': case '/':
				while(!SIsEmpty(&stack) && 	WhoPrecOp(SPeek(&stack), tok) >= 0) {
					convExp[idx++] = SPop(&stack);
				} // 스택에 가장 위에 있는 연산자를 비교해서 연산자를 꺼냄
				SPush(&stack, tok);
				break;
			} // 스택의 연산자 우선 순위를 비교하여 처리
		} // 연산자일 경우
	} // 원본 수식의 문자를 처리

	while(!SIsEmpty(&stack))
		convExp[idx++] = SPop(&stack);		// 스택에 있는 연산자를 수식으로 옮김

	strcpy(exp, convExp);			// 변경된 수식을 원본 수식에 덮어씀
	free(convExp);
}

 

후위 표기법 수식의 계산

- 연산자가 나올때까지 왼쪽부터 조회

- 연산자 앞에 등장하는 두 피연산자를 가지고 연산하여 대체

- 다음에 연산자가 있다면 앞의 두 피연산자를 연산을 하여 대체하는 것을 반복

- 다음에 있는 것이 피연산자면 다시 연산자를 찾아서 위 과정을 반복

 - 조회한 피연산자들을 스택에 따로 담아 연산자를 만나면 두 피연산자를 pop하고 연산한 결과를 다시 push

 

후위 표기법 수식의 계산 코드

int EvalRPNExp(char exp[])
{
	Stack stack;
	int expLen = strlen(exp);
	int i;
	char tok, op1, op2;

	StackInit(&stack);

	for(i=0; i<expLen; i++)
	{
		tok = exp[i];

		if(isdigit(tok))
		{
			SPush(&stack, tok - '0');     // 아스키 두 값을 빼서 숫자로 변환하여 push
		}
		else
		{
			op2 = SPop(&stack);     // 먼저 꺼낸 값이 두 번째 피연산자
			op1 = SPop(&stack);

			switch(tok)
			{
			case '+':
				SPush(&stack, op1+op2);
				break;
			case '-':
				SPush(&stack, op1-op2);
				break;
			case '*':
				SPush(&stack, op1*op2);
				break;
			case '/':
				SPush(&stack, op1/op2);
				break;
			} // 해당 연산자로 연산한 결과를 다시 push
		}
	}
	return SPop(&stack);		// 연산이 끝난 결과를 담고 있는 스택에서 pop하여 반환
}