자료구조 - 전위, 중위, 후위 표기법

전위, 중위, 후위 표기법을 정리해보고자 한다.

 

전위, 중위, 후위 표기법

위 3가지 표기법의 차이점은 연산자의 위치이다.

전위 표기법(Prefix)은 연산자가 피연산자 앞에,

중위 표기법(Infix)은 연산자가 피연산자 사이에,

후위 표기법(Postfix)은 연산자가 피연산자 뒤에 온다.

 

1 + 2 * (3 - 4) * 5라는 식을 예로 들었을 때

전위 표기법은 + 1 * * 2 - 3 4 5

후위 표기법은 1 2 3 4 - * 5 * +이다.

 

이제 어떻게 변환이 되는 것인지 알아보자.

 

중위 표기법을 전위 표기법 & 후위 표기법으로

중위 표기법을 전위, 후위 표기법으로 바꾸는데 가장 많이 쓰이는 방법은 괄호를 이용하는 것이다.

먼저 전위 표기법의 변경 순서는 다음과 같다.

1. 연산 순서대로 괄호를 묶는다.
2. 각 연산자를 괄호 앞으로 뺀다.
3. 괄호를 지운다.

이를 적용해 보자.

1 + 2 * (3 - 4) * 5

>  (1 + ((2 * (3 - 4)) * 5)) : 연산 순서대로 괄호를 묶는다. 
>  + (1 * ( * (2 - (3 4)) 5)) : 각 연산자를 괄호 앞으로 뺀다.

>  + 1 * * 2 - 3 4 5 : 괄호를 지운다.

 

 

후위 표기법도 위와 거의 같다.

1. 연산 순서대로 괄호를 묶는다.
2. 각 연산자를 괄호 뒤로 뺀다.
3. 괄호를 지운다.

이를 적용해 보자.

1 + 2 * (3 - 4) * 5

>  (1 + ((2 * (3 - 4)) * 5)): 연산 순서대로 괄호를 묶는다. 
>  (1 ((2 (3 4) - ) * 5) *) +: 각 연산자를 괄호 뒤로 뺀다.

>  1 2 3 4 - * 5 * +: 괄호를 지운다.

 

생각보다 많이 간단하다는 것을 알 수 있다.

 

 

전위 표기법 & 후위 표기법을 중위 표기법으로

그렇다면 이번엔 반대로 하는 방법을 알아보자.

먼저 전위 표기법을 중위 표기법으로 변환하는 방법이다.

1. 연속된 피연산자 2개와 왼쪽의 연산자 1개를 괄호로 묶는다.
2. 연산자를 피연산자 가운데로 옮긴다.
3. 필요 없는 괄호를 없앤다.

이를 적용해 보자.

+ 1 * * 2 - 3 4 5

>  (+ (1 (* (* 2 (- 3 4)) 5))): 연속된 피연산자 2개와 왼쪽의 연산자 1개를 괄호로 묶는다.

>  ((1 + ((2 * (3 - 4)) * 5))): 연산자를 피연산자 가운데로 옮긴다.

>  1 + 2 * (3 - 4) * 5: 필요 없는 괄호를 없앤다.

 

피연산자 2개와 연산자 1개의 결과는 피연산자 1개이므로 괄호를 (* 2 (- 3 4))처럼 묶을 수 있다.

 

후위 표기법을 중위 표기법으로 변환하는 방법은 위와 거의 같다.

1. 연속된 피연산자 2개와 오른쪽의 연산자 1개를 괄호로 묶는다.
2. 연산자를 피연산자 가운데로 옮긴다.
3. 필요 없는 괄호를 없앤다.

이를 적용해 보자.

1 2 3 4 - * 5 * +

>  (1 ((2 (3 4 -) *) 5 *) +): 연속된 피연산자 2개와 오른쪽의 연산자 1개를 괄호로 묶는다.

>  (1 + ((2 * (3 - 4)) *5)): 연산자를 피연산자 가운데로 옮긴다.

> 1 + 2 * (3 - 4) * 5: 필요 없는 괄호를 없앤다.