Postfix Evaluation, 후위표기식 연산

 

 

Postfix로 작성된 수식을 STACK을 이용하여 연산하는 프로그램을 작성해 보았다.

 

보고서 및 전체 소스 다운로드

 

 

 

 

연산과정은 다음과 같다.

 

예를들어 8/2-3 이라는 Infix방식의 수를 82/3- 의 Postfix방식으로 바꾼뒤 STACK을 이용하여 연산을 하게 되면

 

연산될 두 숫자를 STACK에 저장하고 연산자를 만났을 때 연산, 결과를 다시 STACK에 넣는다.

 

같은 방식으로 식이 종료될 때 까지 반복하면 STACK에는 전체의 연산 결과가 저장될 것이고, 이를 결과로 출력해 준다.

int calculate(char *oper) {
	
	int i=0;
	int j;
	int temp = 0; // 연산된 값을 저장하기 위한 temp 변수
	int temp_mul = 1; // 제곱 연산을 하기 위한 변수


	while(oper[i] != 0) // oper[i] 가 null값, 즉 배열의 마지막 값을 만나면 반복문 종료
	{					// 배열의 마지막 값이 0으로 입력되어 0으로 해주었다.
		
		if(isdigit(oper[i])) // isdigit() -> 배열 값이 정수일때 return 1
		{
			push(oper[i] - '0'); // character 문자형을 정수형으로 바꾸어 주기 위해
								 // ASCII 코드값에서 '0'을 빼주어 push 시킨다.
		}
		else // 배열값이 정수가 아닌 문자일 때
		{
			switch(oper[i])
			{
			case '+': // 더하기 연산
				temp = stack[top-1] + stack[top]; // stack에 들어있는 두 숫자를 더해서 temp에 저장
				// 현재 top index 이전 값과 현재 top index값 두개를 더한다.
				pop(); 
				pop(); // 두 숫자를 더했기 때문에 두번 pop 시킨다.
				push(temp); // temp 값을 다시 push 시킨다.
				break;
			
			case '-': // 빼기 연산
				temp = stack[top-1] - stack[top];
				pop();
				pop();
				push(temp);
				break;

			case '*': // 곱하기 연산
				temp = stack[top-1] * stack[top];
				pop();
				pop();
				push(temp);
				break;

			case '/': // 나누기 연산
				if(stack[top] == 0)
				{
					printf("0으로 나눌 수 없습니다.\n");
					exit(1);
				} // 나눌 숫자가 0일 경우 나눌 수 없기 때문에 에러메시지 출력후 프로그램 종료
				else
				{
					temp = stack[top-1] / stack[top];
					pop();
					pop();
					push(temp);
				}
				break;

			case '%': // 나머지 연산
				if(stack[top] == 0)
				{
					printf("0으로 나눌 수 없습니다.\n");
					exit(1);
				} // 나눌 숫자가 0일 경우 나눌 수 없기 때문에 에러메시지 출력후 프로그램 종료
				else
				{
					temp = stack[top-1] % stack[top];
					pop();
					pop();
					push(temp);
				}
				break;


			case '^': // 제곱연산
				for(j=0;j<stack[top];j++)
				{
					temp_mul = temp_mul * stack[top-1];
				} // 제곱을 만나면 제곱 수 만큼 반복해서 곱해준뒤 변수에 저장한다.
				pop();
				pop();
				push(temp_mul);
				break;


			default:
				printf("알수없는 연산자가 있습니다.\n"); 
				// 알수없는 연산자가 있을 경우 에러메시지 출력후 프로그램 종료
				exit(1);
				break;

			}
		}

		i++;
	}


	return stack[0];
	
}

Calculate라는 Integer형 함수를 만들어 연산 식이 저장되어있는 파일로 부터 식을 읽어와 함수로 넘겨주었다.

 

함수내에서는 STACK을 이용하여 식을 연산하고 최종적으로 STACK의 [0]번째 index, 즉 최종값을 return 시켜 주었다.

 

 

위와 같은 input data를 txt파일로 작성한 뒤 프로그램을 실행시켰을 때

 

 

 

위와 같은 연산 결과를 얻어 낼 수 있었다.

 

보고서 및 전체 소스 다운로드