[문제해설] 다음 수식 A/B-C*D를 Postfix로 표시하시오.

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

---

다음 수식 A/B-C*D를 Postfix로 표시하시오.

 

 

 

 

---

- 문제 해설 -

수식 표기법은 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+'가 되는 것입니다.

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

 

문제에서 제시한 A/B-C*D 식은 수학에서 흔히 쓰이는 중위 표기법(infix)입니다. 이를 먼저 트리로 만들어야 합니다.

수학에서와 마찬가지로 연산자에는 우선순위가 있습니다. *와 /는 +와 - 보다 우선 순위가 높습니다. 같은 우선 순위 레벨의 경우 왼쪽의 것을 우선 연산하는 것이 일반적입니다. 그리고 infix의 표기순서는 'left → root → right'입니다.

A/B-C*D ← 우선 가장 오른쪽에 있으며 우선순위도 높은 붉은색으로 표시된 부분을 3개의 노드로 된 트리로 표현합니다.

A/B

A/B-C*D ← 그다음은 파란색으로 표시된 트리를 그립니다. *가 -보다 우선순위가 높기 때문에 먼저 처리합니다.

A/B 와 C*D

A/B-C*D ← 마지막으로 - 연산자는 A/B와 C*D를 자식으로 가지고 있는 형태입니다.

 

A/B-C*D

이렇게 'A/B-C*D'의 전체 트리가 완성되었습니다.

그럼 이제 위 트리를 Postfix(후위)로 순회하겠습니다. Postfix 표기법은 'left→right→root'순으로 순회합니다.

 

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

 

파란색 부분이 서브루틴입니다. 이 부분을 Postfix로 순회를 하면 AB/ 순으로 순회를 합니다.

그럼 파란색의 서브루틴은 종료가 되고, 원래 붉은색 루트로 복귀하여 순회를 이어갑니다.

붉은색 루프에서는 left까지 순회가 완료된 상태이고, 그다음 right에 해당되는 '*'을 순회해야 하는데, '*'는 자식 노드를 가지므로 인터럽트가 발생합니다.

그럼 초록색에 해당하는 서브루틴을 순회합니다. Postfix로 순회를 하면 CD* 순으로 순회를 합니다. 앞서 순회한 것과 이어서 쓰면 AB/CD*입니다.

그럼 서브 루프을 종료하고 상위 루프로 복귀하면 남은 건 root인 '-'입니다. 

이렇게 순회를 마치면 정답은 AB/CD*-가 됩니다.

 

 

 

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

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