Infix to Postfix - 중위표기식을 후위표기식으로 변환

괄호가 없는 식일 때 Infix (중위표기식)에서 Postfix (후위표기식) 로 바꾸는 방법을 구현해 보았다.

이 과정에서는 연산자의 위치를 결정하기 위해 STACK을 이용하였다.

보고서 및 전체 소스 다운받으러 가기

예를들어 a+b*c 라는 식을 후위표기식으로 변환한다고 해보자.

연산자를 위한 STACK을 만들고 연산자를 만났을 때 STACK에 저장한다.

이 과정에서 연산자의 우선순위를 생각해 주어야 하는데, 우선순위는 우리가 일반적으로 알고 있는것과 같이 *,/ 가 +,- 보다

더 높은 경우들을 생각하면 된다.

이러한 우선순위를 적용하기 위해 프로그램 내에서 따로 우선순위를 결정해주는 함수를 만들어 주었다.

int Oper_order(char oper) //스택 내부의 연산자의 우선순위 { if(oper == '+') { return 1; } else if(oper == '-') { return 1; } else if(oper == '*') { return 2; } else if(oper == '/') { return 2; } else if(oper == '%') { return 2; } else if(oper == '^') { return 3; } else { return -1; } }

다음과 같은 함수를 만들어 주고, parameter로 연산자 문자를 받으면 그 문자가 어떤 문자인지에 따라서

우선순위를 return 해 주는 형식이다.

제곱인 ^를 우선순위가 제일 높은 3으로, *, /, % 연산을 2로, +, -를 1로 return 될수 있게 해주었으며 그 외에는 -1이 return되게

하여 예외처리를 해 주었다.

연산과정에서 연산자 STACK의 Top에 있는 연산자 우선순위를 검사한다.

그 뒤에 STACK에 새롭게 들어올 연산자의 우선순위를 검사한뒤 두개를 비교하고, 

Top에 있는 연산자 우선순위가 새롭게 들어올 연산자의 우선순위보다 더 작을 때

새로운 연산자는 STACK에 들어오게 된다.

반대로 새롭게 들어올 연산자의 우선순위가 Top에 있는 연산자 우선순위보다 더 낮거나 같으면 

먼저 Output에 현재 연산자 STACK top위치에 있는 연산자를 pop해서 출력해주고, 

새로들어온 연산자를 다시 연산자 STACK에 push해준다.

식을 모두 검사한 뒤에는 연산자 STACK에 있는 연산자들을 차례대로 Pop해주어 Ouput에 연결해 준다.

이제 Output을 출력하면 Postfix 된 식이 출력될 것이다.

void Trans(char* data) { //char temp[SIZE]; // Postfix로 변환된 Output이 저장될 배열 // char* _Trans; int i = 0; int j = 0; while(data[i] != 0) { if(isdigit(data[i])) // 받아온 문자가 정수일 경우 { // 정수가 들어올 경우 temp배열에 저장한다. // 저장할때는 char 형으로 저장되어야 한다. temp[j++] = data[i]; } else // 받아온 문자가 정수가 아닐 경우, 즉 연산자일 경우 { // 정수가 아닌 연산자가 들어올 경우에는 우선순위를 비교해 가며 스택을 이용한다. if(oper_top == -1) { // operation stack의 top index가 -1일 경우 스택이 비어있음을 의미 oper_push(data[i]); } else { // operation stack에 하나이상의 연산자가 들어있을 경우 if(Oper_order(data[i]) > Oper_order(oper_stack[oper_top])) { // 현재 oper_stack의 top위치에 들어있는 연산자와 새로 입력받은 연산자의 // 우선순위를 비교하여 새로 입력받은 연산자의 우선순위가 더 클 경우 oper_push(data[i]); // oper stack에 연산자를 push 해준다 } else if(Oper_order(data[i]) <= Oper_order(oper_stack[oper_top])) { // 현재 oper_stack의 top위치에 들어있는 연산자와 새로 입력받은 연산자의 // 우선순위를 비교하여 새로 입력받은 연산자의 우선순위가 같거나 더 작을 경우 temp[j++] = oper_stack[oper_top]; // output에 현재 oper stack에 저장되어있는 연산자를 저장 oper_pop(); // operstack을 pop oper_push(data[i]); // 새로 들어온 연산자를 operstack에 다시 push } } } i++; } // 반복문이 종료된 뒤 while(oper_top > -1) { temp[j++] = oper_stack[oper_top]; oper_pop(); } // oper stack에 남아있는 연산자들을 뒤에서부터 output 결과에 넣어준다. }

결과를 출력해 보면

먼저 input data가 다음과 같을 때

Output으로 출력되는 결과 역시 제대로 출력되는 것을 확인할 수 있었다.

보고서 및 전체 소스 다운받으러 가기