부산대학교자료구조
Scientific Inference Lab

When Do We Visit the Root

Parse Trees

parse tree는 연산자를 내부 노드에, 수를 단말 노드에 두어 식의 계산 순서를 나타내는 이진트리다. 값 계산에는 두 자식 노드 결과가 먼저 필요한 후위 순회를, 식 출력에는 원래 순서를 복원하는 중위 순회를 쓴다.

연산자와 피연산자한 연산자의 왼쪽과 오른쪽 부분 트리가 두 피연산자를 나타낸다.
만들기식을 읽으며 자식 노드로 내려가기 전에 현재 노드를 스택에 push하고 돌아올 때 pop한다.
계산과 출력후위 순회는 값을 계산하고, 중위 순회는 괄호와 함께 식을 출력한다.

후위 순회로 계산하면 두 자식 노드의 값이 부모 노드보다 먼저 준비된다

((7 + 3) × (5 − 2))의 parse tree에서 처리한 노드 수를 옮기면 후위 순회로 처리한 노드와 그 노드가 반환한 값이 바뀐다.

후위 순회 계산parse tree와 노드별 반환값
회색 원은 연산자 노드, 흰 원은 수가 든 단말 노드다. 초록으로 채운 원이 방금 처리한 노드, 옅은 파란 원이 이미 처리한 노드이며 원 아래 초록 수가 그 노드가 반환한 값이다.

식을 한 기호씩 읽으며 트리를 만들고 스택으로 부모 노드에 돌아간다

(3 + (4 × 5))를 읽는다. 읽은 기호 수를 옮기면 기호에 따른 동작, 현재 위치, 스택에 쌓인 부모 노드가 바뀐다.

parse tree 만들기읽은 기호와 트리, 스택
맨 위 줄은 입력 기호이며 초록 칸이 방금 읽은 기호, 파란 칸이 이미 읽은 기호다. 트리에서 초록 굵은 테두리가 현재 위치, 점선 원이 아직 값이 없는 노드다. 오른쪽 기둥은 부모 노드를 기억하는 스택이며 위가 맨 위다.

같은 parse tree도 순회 방식에 따라 계산 결과나 다른 표기가 나온다

((7 + 3) × (5 − 2))의 parse tree에서 순회 방식을 바꾸면 노드를 처리하는 순서와 그 순서로 만든 출력이 바뀐다.

순회가 노드를 처리한 순서대로 이어 붙인 출력이다. 중위 순회는 연산자 노드마다 앞뒤에 괄호를 붙이고, print_exp 그대로 출력하면 수 노드에도 괄호가 붙는다.