[문제해설] 다음 Postfix로 표현된 수식 AB/CD×-을 Infix 표기법으로 변환하시오.

전자계산기조직응용기사 실기 필답형 기출문제 (수식 표기법) - 2010년1회, 2013년3회

---

다음 Postfix로 표현된 수식 AB/CD×-을 Infix 표기법으로 변환하시오.

 

 

---

 

- 문제 해설 -

수식 표기법은 2진 트리 순회 문제와 같습니다. 단지 노드의 값들이 숫자와 연산자로 이루어져 있을 뿐입니다.

먼저 순회 방법의 대해 알아보겠습니다.

 

표기법	순회순서
전위(Prefix)	root → left → right
중위(infix)	left → root → right
후위(postfix)	left → right → root
인터럽트 조건 : 순회하는 노드가 자식노드가 있을 때.

위처럼 3개의 노드로 이루어진 2진 트리 순회는 전, 중, 후위 순회가 있으며, 그 기준은 root 노드의 순회 순서라는 것을 알 수 있습니다.

그리고 수식 표기법은 아래와 같습니다.

이렇게 3개의 노드로 구성된 수식표기법은 root가 연산자이고, 두 개의 자식 노드는 값(순자)을 가집니다.

일반적으로 수학에서 쓰는 표기법은 중위(infix) 표기법입니다. 예를 들어 '2+3'을 3개의 노드로 이루어진 이진트리로 표현하면 다음과 같습니다.

위 트리를 전위(prefix) 표기법으로 표현을 하려면 'root → left → right' 순으로 순회를 해서 '+23'가 됩니다.

그리고 중위(infix) 표기법은 'left → root → right' 순으로 순회를 해서 '2+3'이 되고,

후위(postfix) 표기법은 'left → right → root' 순으로 순회를 해서 '23+'가 되는 것입니다.

물론 수식 표기법에서의 트리 순회도 인터럽트가 조건이 있습니다. 당연히 자식 노드를 가질 때겠지요. 이는 문제를 풀어보면서 살펴보겠습니다.

 

문제에서 제시한 postfix표기법으로 작성된 'AB/CD×-'을 먼저 트리로 만들겠습니다.

Postfix의 표기순서는 'left → right → root'가 됩니다. 그럼 문제에서 제시한 식을 3개씩 보겠습니다.

AB/CD×-  ← 먼저 붉은색으로 표시된 3개의 노드를 트리로 표현합니다.

AB/

그다음 AB/CD×-  ← 파란색으로 표기된 트리도 옆에 그립니다.

 

AB/CDX

마지막으로 AB/CDX- ← 마지막의 연산자 -는 위에서 그린 두 개의 트리를 자식으로 가지겠네요. 트리로 표현하면 다음과 같습니다.

AB/CDX-

이렇게 'AB/CD×-'의 전체 트리가 완성되었습니다. 
그럼 이제 위 트리를 Infix(중위)로 순회하겠습니다. Infix 표기법은 'left → root → right' 순으로 순회합니다.

먼저 root가 포함된 붉은색으로 표시한 3개의 노드를 기준으로 infix로 순회를 하면 먼저 left인 '/'를 순회해야 되는데... '/'는 자식 노드를 가지므로 인터럽트가 발생합니다. 순회를 잠시 멈추고,

그럼 파란색 부분이 서브루틴이 되겠죠? 이 부분을 infix로 순회를 하면 A/B 순으로 순회를 합니다.

그럼 파란색의 서브루틴은 종료가 되고, 원래 붉은색 루프로 돌아가서 순회를 계속합니다.

붉은색 루프에서는 left까지 순회가 완료된 상태이고, 그다음 root에 해당되는 '-'를 순회합니다.(지금까지 A/B-)

마지막으로 right에 해당하는 '×'를 순회할려는데... 'x'는 자식 노드를 가지므로 인터럽트가 발생합니다.

그럼 초록색의 해당하는 서브루틴을 순회하겠습니다. 먼저 left에 해당하는 'C'를 순회한 후 root에 해당하는 '×'를 순회하고, right에 해당하는 'D'를 순회합니다. (지금까지 A/B-C×D)

그럼 모든 순회가 마쳤습니다. 

정답은 A/B-C×D 가 되겠습니다.

 

 

 

https://youtube.com/playlist?list=PLboXycXmAIDt4ObBRPVj29BuD2d27oRnO

전자계산기조직응용기사 실기 필답형