션팅 야드 알고리즘

우리가 작성하는 모든 수학 표현식은 *중위 표기법(infix notation)*으로 표현된다. 예를 들어:

A + B * C

연산자가 피연산자 사이에 위치하기 때문에 이 표현식은 중위 형식이라고 한다. 생각해보면, 종이에 적는 모든 표현식은 항상 중위 형식이다. 이것이 우리 인간이 이해하는 방식이다.

곱셈은 덧셈보다 우선순위가 높기 때문에, 위의 표현식을 평가할 때 먼저 B와 C를 곱한 다음 그 결과를 A에 더한다. 우리 인간은 연산자의 우선순위를 쉽게 이해할 수 있지만, 기계는 각 연산자에 대한 명확한 지시가 필요하다.

평가 순서를 바꾸기 위해 괄호를 사용할 수 있다:

(A + B) * C

이제 A와 B를 먼저 더한 다음 그 합을 C와 곱한다.

중위 표기법으로 작성된 표현식을 파싱하고 평가하는 알고리즘을 작성한다면, 이 과정이 매우 번거롭다는 것을 깨닫게 될 것이다. 어떤 연산을 먼저 수행해야 하는지 알기 위해 표현식을 여러 번 파싱해야 한다. 연산자의 수가 늘어날수록 복잡도도 증가한다.

후위 표기법

후위 표기법(Postfix notation)은 역폴란드 표기법(Reverse Polish Notation, RPN)으로도 알려져 있다. 이 표기법에서는 연산자가 해당 피연산자 뒤에 위치한다. 이전 섹션의 예제를 후위 표기법으로 표현하면 다음과 같다:

A B C * +

후위 표기법으로 표현된 식에는 괄호가 없으며, 연산자 우선순위를 고민할 필요도 없다. 이는 컴퓨터가 식을 평가하기 쉽게 만든다. 연산자를 적용해야 하는 순서가 정해져 있기 때문이다.

후위 표기법으로 표현된 식을 평가하는 방법은 스택을 사용해 쉽게 구현할 수 있다. 다음은 이를 위한 의사코드이다:

1. 후위 표기법 식을 토큰 단위로 읽는다.
2. 토큰이 피연산자라면 스택에 푸시한다.
3. 토큰이 이항 연산자라면,
   1. 스택에서 가장 위에 있는 두 피연산자를 팝한다.
   2. 이항 연산자를 두 피연산자에 적용한다.
   3. 결과를 다시 스택에 푸시한다.
4. 마지막에는 전체 후위 표기법 식의 값이 스택에 남는다.

위 의사코드를 사용해 A B C * + 를 평가하는 과정은 다음과 같다:

식	스택
A B C * +
B C * +	A
C * +	A, B
* +	A, B, C
+	A, D
	E

여기서 D = B * C 이고, E = A + D 이다.

위에서 볼 수 있듯이, 후위 표기법 연산은 연산자를 적용해야 하는 순서가 미리 정해져 있기 때문에 비교적 쉽게 평가할 수 있다.

중위 표기법을 후위 표기법으로 변환하기

중위 표기법을 후위 표기법으로 변환하기 위해 에츠허르 다익스트라가 고안한 알고리즘이 바로 션팅 야드 알고리즘이다. 많은 계산기에서 이 알고리즘을 사용해 입력된 수식을 후위 표기법으로 변환한다.

다음은 이 알고리즘의 의사 코드다:

1. 모든 입력 토큰에 대해:
   1. 다음 토큰을 읽는다
   2. 토큰이 연산자(x)라면:
      1. 연산자 스택의 맨 위에 연산자(y)가 있고, (x)가 왼쪽 결합성을 가지며 우선순위가 (y)보다 작거나 같거나, (x)가 오른쪽 결합성을 가지며 우선순위가 (y)보다 작다면:
         1. 스택에서 (y)를 꺼낸다
         2. (y)를 출력 버퍼에 추가한다
      2. (x)를 스택에 넣는다
   3. 토큰이 왼쪽 괄호라면, 스택에 넣는다
   4. 토큰이 오른쪽 괄호라면:
      1. 스택의 맨 위 토큰이 왼쪽 괄호가 될 때까지 스택에서 꺼내 출력 버퍼에 추가한다
      2. 왼쪽 괄호를 꺼내지만 출력 버퍼에는 추가하지 않는다
   5. 그 외의 경우 토큰을 출력 버퍼에 추가한다
2. 스택에 남아 있는 모든 연산자 토큰을 출력 버퍼에 추가한다

간단한 예제를 통해 이 의사 코드가 어떻게 동작하는지 살펴보자. 다음은 변환할 중위 표현식이다:

4 + 4 * 2 / ( 1 - 5 )

다음 표는 각 연산자의 우선순위와 결합성을 나타낸다. 알고리즘에서도 동일한 값을 사용한다.

연산자	우선순위	결합성
^	10	오른쪽
*	5	왼쪽
/	5	왼쪽
+	0	왼쪽
-	0	왼쪽

변환 과정은 다음과 같다:

토큰	동작	출력	연산자 스택
4	토큰을 출력에 추가	4
+	토큰을 스택에 넣음	4	+
4	토큰을 출력에 추가	4 4	+
*	토큰을 스택에 넣음	4 4	* +
2	토큰을 출력에 추가	4 4 2	* +
/	스택에서 꺼내 출력에 추가, 토큰을 스택에 넣음	4 4 2 *	/ +
(	토큰을 스택에 넣음	4 4 2 *	( / +
1	토큰을 출력에 추가	4 4 2 * 1	( / +
-	토큰을 스택에 넣음	4 4 2 * 1	- ( / +
5	토큰을 출력에 추가	4 4 2 * 1 5	- ( / +
)	스택에서 꺼내 출력에 추가, 스택에서 꺼냄	4 4 2 * 1 5 -	/ +
끝	스택 전체를 출력에 추가	4 4 2 * 1 5 - / +

최종적으로 얻은 후위 표현식은 다음과 같다:

4 4 2 * 1 5 - / +

함께 보기

위키백과의 Shunting yard 알고리즘

Swift Algorithm Club의 Ali Hafizji가 작성함
Jaap Wijnen이 Swift 3로 마이그레이션함