[문제해설] Infix 표기의 식 (A/(B^C))*D＋E를 Postfix 방법으로 바르게 표현한 것은?

전자계산기조직응용기사 필기 기출문제 (2과목 자료구조 및 데이터통신-트리) - 2016년1회

---

Infix 표기의 식 (A/(B^C))*D＋E를 Postfix 방법으로 바르게 표현한 것은?

 

① ＋*/A^BCDE         ② ABC^/D*E＋

③ E＋D*C^B/A         ④ AB^/CD*E＋

 

 

 

---

- 문제 해설 -

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

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

 

문제에서 주어진 식은 중위 표기(infix)로 쓰인 '(A/(B^C))*D＋E'입니다. 이를 먼저 트리로 만들어야 합니다.

수학에서와 마찬가지로 연산자에는 우선순위가 있습니다. 가장 우선순위가 높은 것은 괄호( )이고, 그다음 *와 /, +와 - 순입니다. 동등한 우선순위의 경우 왼쪽의 것이 순위가 더 높습니다.(표준 C언어) 그리고 infix의 표기순서는 'left → root → right'입니다.

(A/(B^C))*D＋E ← 가장 우선순위가 높은 붉은색으로 표시된 부분을 3개의 노드로 된 트리로 표현합니다.

B^C

(A/(B^C))*D＋E ← 그다음 주황색으로 표시된 부분과 방금 만든 붉은색 부분을 트리로 표현합니다.

(A/(B^C))

(A/(B^C))*D＋E ← 이번에는 앞서 만들어진 트리와 초록색으로 표시된 부분을 트리로 표현합니다.

(A/(B^C))*D

(A/(B^C))*D＋E ← 마지막으로 파란색으로 표시된 부분을 앞서 만든 트리와 함께 표현합니다.

(A/(B^C))*D+E

이제 '(A/(B^C))*D+E'의 전체 트리가 완성되었습니다.

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

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

파란색 부분의 서브루틴을 호출합니다. 이 부분을 Postfix로 순회를 하면 우선 left인 '/'를 순회해야 되는데, 이 또한 자식 노드를 가지므로 인터럽트가 발생합니다.

이번엔 초록색 부분의 서브루틴을 호출합니다. 이 부분을 Postfix로 순회하면 우선 left인 'A'를 순회 완료하고, right인 '^'을 순회해야 하는데, '^'는 자식 노드를 가지므로 또 인터럽트가 발생합니다. 여기까지 순회 결과는 [A]입니다.

이번엔 노란색 부분의 서브루틴을 호출합니다. 이 부분을 Postfix로 순회를 하면 우선 left인 'B'를 순회 완료하고, right인 'C'를 순회 후, root인 '^'를 순회하고 상위 루틴으로 복귀합니다. 여기까지 순회 결과는 [A, B, C, ^]입니다.

초록색 루틴으로 복귀 후 멈추었던 순회를 계속합니다. left와 right의 순회는 이미 완료했고, root인 '/'를 순회하고 상위 루틴으로 복귀합니다. 여기까지 순회 결과는 [A, B, C, ^, /]입니다.

파란색 루틴으로 복귀후 이어서 순회를 합니다. right인 'D'를 순회 후, root인 '*'을 순회하고 상위 루틴으로 복귀합니다. 여기까지 순회 결과는 [A, B, C, ^, /, D, *]입니다.

마지막 최상위 루틴으로 복귀를 했습니다. 이어서 순회를 하면 right인 'E'를 순회하고, 마지막으로 root인 '+'를 순회하면 모든 순회를 마치게 됩니다.

위와 같은 순서로 모든 순회를 마쳤습니다.

그럼 순회 순서대로 값을 나열하면, ABC^/D*E+ 이고, 정답은 2번이 됩니다.

 

 

 

 

https://youtube.com/playlist?list=PLboXycXmAIDuukQ2A6EvMZI-x1IMy3Xc-

전자계산기조직응용기사 필기