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

후위 표기법으로 바꾸는 과정

중위 표기법을 후위 표기법으로 바꾸는 개념은 아래와 같다.

• 문자열 수식을 순회한다.
  • 피연산자를 만나면 출력한다.
  • 연산자를 만나면
    • 스택에 연산자가 있는지 확인한다.
    • 스택의 마지막 연산자가 현재 연산자보다 우선순위가 높으면 pop 하여 출력한다.
  • 현재 연산자를 스택에 추가한다.
• 스택이 빌 때까지 pop하여 출력한다.

 

"3 + 5 * 2"를 후위 표기법으로 변환

위의 과정을 따라가면서 "3 + 5 * 2"를 후위 표기법으로 바꿔보자.

 

피연산자

352

 

연산자

+*

 

연산자는 스택 구조로 저장된다. 

 

>> 3

>> 35

>> 352

>> 352*+

 

352*+

 

(*의 우선순위가 더 높으므로 *가 pop 되지 않고 그대로 스택 되어서 마지막에 출력된다.)

 

"3 * 5 + 2"를 후위 표기법으로 변환

피연산자

352

 

연산자

*+

 

연산자는 스택 구조로 저장된다.

 

35가 출력된 상황에서 기존 스택의 * 우선순위가 + 보다 높으므로 *가 바로 출력된다.

>> 35* (*가 출력)

>> 35*2

>> 35*2+

>> 변환 완료

 

35*2+

 

참고 사이트

04-03. 후위 표기법(Postfix notation) #1