infix -> postfix

연산자의 infix 표기를 postfix로 바꿀 때에는 대개 스택을 이용합니다. 

간단하게 설명드리자면, 모든 수식을 연산자, 피연산자로 구분합니다. 

이때, 연산자, 피연산자 각각이 하나의 단위로 동작하게 됩니다.

1. 수식에서 첫번째 항목을 빼냅니다.

2. 수식의 빼낸 항목이 피연산자라면 그대로 출력측으로 빼냅니다

3. 수식의 빼낸 항목이 연산자라면 스택의 최상위 원소와 비교합니다.

4. 빼낸 연산자의 우선순위가 스택의 최상위에 있는 원소보다 높으면 그대로 스택에 넣습니다.

5. 그렇지 않다면 스택의 최상위 원소를 출력측으로 뺴내고 빼낸 연산자를 스택에 넣습니다.

6. 단, 여는 괄호'('가 나오면 닫는괄호')'가 나올 때까지 스택에 남아있게 되며, 닫는괄호')'가 나타나면 그때까지 여는괄호'('보다 상위에 있는 모든 연산자를 출력측으로 빼냅니다.

이런 알고리즘으로 간단히 infix표기를 postfix표기로 바꿀 수 있습니다.

간단한 예를 들어 보지요. 모든 표기는 입력측, 스택, 출력측으로 분리해서 표시하겠습니다.

0. 초기상태

입력 : 1 + 2 * 3 + ( 4 * 5 + 6 )

스택 : [empty]

출력 : [empty]

1. 입력에서 한개의 토큰을 받습니다. 이때, 입력측에서 1이 나오며, 이는 피연산자이므로 바로 출력측으로 갑니다.

입력 : + 2 * 3 + ( 4 * 5 + 6 )

스택 : [empty]

출력 : 1

2. 이제 입력측의 제일 앞에는 +가 있습니다. 연산자이므로 스택에 넣습니다. 이때, 우선순위를 비교할 대상이 스택에 존재하지 않으므로 바로 스택에 들어갑니다.

입력 : 2 * 3 + ( 4 * 5 + 6 )

스택 : +

출력 : 1

3. 2를 꺼내옵니다. 피연산자이므로 바로 출력측으로 갑니다.

입력 : * 3 + ( 4 * 5 + 6 )

스택 : +

출력 : 1 2

4. *를 꺼내옵니다. 연산자이므로 스택에 있는 연산자와 우선순위를 비교하여 *의 우선순위가 더 높으므로 그대로 스택에 넣습니다.

입력 : 3 + ( 4 * 5 +6 )

스택 : + *

출력 : 1 2

5. 3을 꺼냅니다. 피연산자이므로 출력측으로 갑니다. (앞으로 피연산자는 그냥 출력측으로 간다는 것을 생략하겠습니다)

입력 : + ( 4 * 5 + 6 )

스택 : + *

출력 : 1 2 3

6. +를 꺼냅니다. 연산자이므로 스택에 있는 연산자와 우선순위를 비교합니다. 방금 꺼낸 연산자보다 우선순위가 낮은 연산자가 나올때까지 스택에 있는 연산자를 pop하여 출력측으로 보냅니다. 그 결과로 처음에 *가, 그 다음에 +가 출력측으로 보내지고, 방금꺼낸 +가 스택에 들어갑니다.

입력 : ( 4 * 5 + 6 )

스택 : +

출력 : 1 2 3 * +

6. '('를 꺼냅니다. 여는괄호이므로 그냥 그대로 스택에 넣습니다.

입력 : 4 * 5 + 6 )

스택 : + (

출력 : 1 2 3 * +

7. 4를 꺼냅니다

입력 : * 5 + 6 )

스택 : + (

출력 : 1 2 3 * + 4

8. *를 꺼냅니다. 연산자이므로 스택의 최상위 연산자와 비교를 수행합니다. 스택의 최상위에 (가 있으므로 (여는 괄호는 가장 높은 우선순위를 가지는 것으로 가정합니다) 그냥 스택에 들어갑니다.

입력 : 5 + 6 )

스택 : + ( *

출력 : 1 2 3 * + 4

9. 5를 빼냅니다.

입력 : + 6 )

스택 : + ( *

출력 : 1 2 3 * + 4 5

10. +를 빼냅니다. 스택의 최상위 연산자와 우선순위를 비교합니다. *의 우선순위가 더 높으므로 *가 빠져나온 다음 +가 스택에 들어갑니다.

입력 : 6 )

스택 : + ( +

출력 : 1 2 3 * + 4 5 *

11. 6을 빼냅니다.

입력 : )

스택 : + ( +

출력 : 1 2 3 * + 4 5 * 6

12. )를 빼냅니다. 이때, 닫는 괄호가 나왔으므로 스택에서 여는 괄호가 나올때까지 스택에 있는 연산자를 모두 pop합니다.

입력 : [empty]

스택 : +

출력 : 1 2 3 * + 4 5 * 6 +

13. 입력이 모두 비워졌으므로 스택이 비워질때까지 pop합니다.

입력 : [empty]

스택 : [empty]

출력 : 1 2 3 * + 4 5 * 6 + +

이런 식으로 후위표기로 바꿀 수 있습니다. 

만약 스택에 대한 내용이 이해가 안가신다면 자료구조 책을 보시기 바랍니다. 모든 자료구조책의 첫부분은 스택에 대한 내용이 반드시 있으며, 또한 스택을 설명하면서 반드시 postfix 변환이 예로 나와 있습니다.