트리와 순회·수식 표기법 2

앞 문서의 전위·중위·후위 순회(traversal)와 같은 원리로 수식도 세 가지로 적을 수 있다. 시험은 중위 표기식을 후위·전위로 바꾸거나 후위식을 중위로 되돌리게 하고, 후위 표기식을 스택(stack)으로 계산한 값도 묻는다.

수식 표기법

수식도 연산자를 노드(트리의 한 칸)로, 피연산자를 잎(자식이 없는 끝 노드)으로 둔 트리로 볼 수 있다. 그 트리를 전위 순회(preorder)로 읽으면 전위 표기법(prefix notation), 중위 순회(inorder)로 읽으면 중위 표기법(infix notation), 후위 순회(postorder)로 읽으면 후위 표기법(postfix notation)이 된다. 사람이 평소 쓰는 식은 중위 표기법이다.

표기법	연산자 위치	A*(B+C)-D/E
전위 표기법	피연산자 앞	-*A+BC/DE
중위 표기법	피연산자 사이	A*(B+C)-D/E
후위 표기법	피연산자 뒤	ABC+*DE/-

중위 표기법을 후위로 바꿀 때는 연산 순서대로 괄호를 모두 친 뒤, 각 연산자를 자기 괄호의 닫는 괄호 자리로 옮기고 괄호를 지운다. 예를 들어 A*(B+C)-D/E는 괄호를 모두 치면 ((A*(B+C))-(D/E))이고, 각 연산자를 닫는 괄호 자리로 옮겨 괄호를 지우면 ABC+*DE/-가 된다. 전위로 바꿀 때는 여는 괄호 자리로 옮긴다. 후위 표기법은 괄호 없이도 계산 순서가 하나로 정해져서 컴퓨터가 계산하기 쉽다.

거꾸로 후위 표기식을 중위로 되돌릴 때는 왼쪽부터 읽다가 연산자를 만날 때마다 바로 앞의 피연산자 두 개와 그 연산자를 괄호 하나로 묶는다. 묶은 덩어리는 다시 피연산자 하나로 본다. 다 묶었으면 각 연산자를 자기 괄호 안의 두 피연산자 사이로 옮기고, 연산자 우선순위(operator precedence)상 필요 없는 괄호를 지운다. 예를 들어 ABC*+DE-/는 ((A(BC*)+)(DE-)/)로 묶이고, 연산자를 가운데로 옮기면 ((A+(B*C))/(D-E)), 괄호를 정리하면 (A+B*C)/(D-E)다.

스택으로 후위 표기식 계산

후위 표기식은 왼쪽부터 읽으며 숫자면 스택에 넣고, 연산자면 두 개를 꺼내 계산한 결과를 다시 넣는다. 먼저 꺼낸 값이 오른쪽 피연산자다. 6 2 3 + * 4 -를 계산하면 다음과 같다.

읽은 것	스택
6, 2, 3	6 2 3
+	6 5
*	30
4, -	26

시험 포인트

• 연산자가 피연산자 앞 전위, 사이 중위, 뒤 후위 표기법.
• 중위 → 후위: 괄호를 모두 치고 연산자를 닫는 괄호 자리로. 전위는 여는 괄호 자리로.
• 후위 → 중위: 피연산자 둘과 연산자를 묶고 연산자를 두 피연산자 사이로, 필요 없는 괄호 제거.
• 후위식 계산: 숫자는 푸시, 연산자를 만나면 두 개를 팝해 나중에 꺼낸 값 연산 먼저 꺼낸 값을 푸시.