후위식

Postfix

• 스택(Stack)을 이용하여 연산자가 뒤에 위치하도록 한 수식
• 사람 입장에선 이해하기 어려우나 컴퓨터 입장에선 계산하기 수월하다

• ex) 3 4 * 5 6 * ＋
  1. 3
  2. 3 4
  3. 3 4 *
  4. 12
  5. 12 5
  6. 12 5 6
  7. 12 5 6 *
  8. 12 30
  9. 12 30 +
  10. 42

세 가지 표기법

표기법	연산자 위치	A + B	(A + B) * C
전위(Prefix, 폴란드 표기법)	피연산자 앞	+AB	*+ABC
중위(Infix)	피연산자 사이	A+B	(A+B)*C
후위(Postfix)	피연산자 뒤	AB+	AB+C*

사람이 읽기 좋은 것은 중위지만, 괄호가 필요하고 우선순위를 알아야 한다. 전위·후위는 괄호 없이도 해석이 유일하다.

중위 → 후위 변환

손으로 푸는 법

1. 연산자 우선순위에 따라 수식 전체를 괄호로 완전히 묶는다.
2. 각 괄호 안의 연산자를 그 괄호의 닫는 괄호 자리로 옮긴다.
3. 괄호를 지운다.

예: (A + B) * C + (D + E)

1) 완전 괄호화 : ( ( (A+B) * C ) + (D+E) )
2) 연산자 이동 : ( ( (A B +) C * ) (D E +) + )
3) 괄호 제거   : A B + C * D E + +

따라서 답은 AB+C*DE++ 다.

스택을 쓰는 알고리즘

조차장 알고리즘(Shunting-yard algorithm)이라 한다. 스택 하나로 처리한다.

• 피연산자는 바로 출력한다.
• 연산자는 스택에 넣되, 스택 꼭대기에 우선순위가 같거나 높은 연산자가 있으면 먼저 꺼내 출력한 뒤 넣는다.
• 여는 괄호는 그냥 넣고, 닫는 괄호를 만나면 여는 괄호가 나올 때까지 꺼내 출력한다.
• 수식이 끝나면 스택에 남은 연산자를 모두 꺼내 출력한다.

후위 수식 계산

역시 스택으로 한다.

• 피연산자를 만나면 스택에 넣는다.
• 연산자를 만나면 스택에서 두 개를 꺼내 연산하고 결과를 다시 넣는다. 이때 먼저 꺼낸 것이 오른쪽 피연산자다.
• 마지막에 스택에 남은 하나가 결과다.

수식 : 3 4 + 5 *
3      → [3]
4      → [3, 4]
+      → 3+4=7      → [7]
5      → [7, 5]
*      → 7*5=35     → [35]
결과 35

참고

• 후위 표기 수식을 수식 트리의 후위 순회 결과로 볼 수 있다. 전위 표기는 전위 순회, 중위 표기는 중위 순회에 대응한다.
• 후위 → 중위 변환은 위 과정을 거꾸로 하면 된다.

같이 보기

• 스택
• 트리
• 이진 트리
• 자료 구조