차량기지 알고리즘

차량기지 알고리즘은 중위 표기법으로 표현된 수식을 분석할 때 사용할 수 있는 알고리즘이다. 알고리즘의 결과물은 역폴란드 표기법이나 파스 트리가 될 수 있다. 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라가 고안하여 1961년에 발표하였다. 데이크스트라는 알고리즘의 동작이 철도 차량기지의 그것을 닮았다고 하여 차량기지 알고리즘이라는 이름을 붙였다.

역폴란드 표기법의 계산법처럼, 차량기지 알고리즘 또한 스택을 이용한다. ${\displaystyle 3+4}$ 또는 ${\displaystyle 3+4\times (2-1)}$처럼 대부분의 사람들에게 익숙한 중위 표기법을 역폴란드 표기법으로 변환하려면 입력, 출력 및 한개의 연산자 스택이 필요하다.

간단한 예제

그림으로 보는 차량기지 알고리즘. 입력은 한번에 하나씩 들어오며, b), d), f), h) 에서처럼 입력이 변수 또는 숫자일 경우 바로 출력으로 옮겨진다. 만약 입력이 연산자라면, 연산자의 우선순위 및 결합 방향에 따라 c), e)처럼 연산자 스택으로 옮겨지거나, g)처럼 즉시 출력으로 옮겨진다. 입력이 모두 완료되면 연산자 스택의 연산자들이 모두 팝되어 출력으로 옮겨진다.

입력: 3+4

1. 첫 번째 입력인 3을 출력 큐로 옮긴다. (숫자가 입력될 때마다 출력으로 옮겨진다)
2. "+" 연산자를 연산자 스택으로 푸쉬한다.
3. 4를 출력 큐로 옮긴다.
4. 입력이 완료되면 연산자 스택에서 연산자들을 팝한 다음 출력으로 옮긴다.
5. 이 경우 연산자 스택의 연산자는 "+" 한개뿐이다.
6. 출력: 3 4 +

이 간단한 예제로부터 몇가지 규칙을 살펴볼 수 있다.

• 입력이 숫자일 경우 바로 출력으로 옮긴다.
• 모든 입력을 읽어들였다면 연산자 스택의 모든 연산자를 팝하여 순서대로 출력으로 옮긴다.

자세한 알고리즘

• 입력이 아직 남아있는 동안

• 입력에서 토큰을 읽어들인다.
• 만약 토큰이 숫자 또는 변수일 경우 출력 큐에 넣는다.
• 만약 토큰이 함수일 경우 연산자 스택에 푸쉬한다.
• 만약 토큰이 함수 인자의 구분자(예: 쉼표)일 경우

• 스택에서 여는 괄호 '(' 가 나타날 때까지 팝하여 출력 큐에 넣는다. 만약 여는 괄호가 나타나지 않으면 구분자의 위치가 잘못되었거나 여는 괄호와 닫는 괄호가 맞지 않는 것이므로 오류를 출력한다.

• 토큰이 연산자 o₁이라면, 연산자 스택의 맨 위에 연산자가 없을 때까지 다음을 반복한다

• 만약 스택에 연산자 o₂가 있다면

o₁이 왼쪽 결합 연산자이고, 연산의 우선순위가 o₂와 같거나 그보다 낮을 경우,

또는 o₁이 오른쪽 결합 연산자이고, 우선순위가 o₂보다 낮을 경우

o₂를 팝하여 출력 큐에 넣는다.

• 만약 스택에 연산자가 없거나 o₂가 조건을 만족하지 않으면 o₁을 연산자 스택에 푸쉬한다.

• 만약 토큰이 여는 괄호 '(' 일 경우 연산자 스택에 푸쉬한다.
• 만약 토큰이 닫는 괄호 ')' 일 경우

• 연산자 스택에서 여는 괄호가 나타날 때까지 연산자를 팝하여 출력 큐에 넣는다.
• 연산자 스택에서 여는 괄호가 나타나면 팝하되, 출력 큐에는 넣지 않는다.
• 스택을 모두 팝할 때까지 여는 괄호를 찾지 못했다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
• 여는 괄호를 팝한 후 스택 맨 위에 함수 토큰이 남아있다면 출력 큐에 넣는다.

• 더 이상 입력 토큰이 남아있지 않다면

• 연산자 스택이 빌 때까지 토큰을 팝한다.

• 만약 스택에 여는 괄호나 닫는 괄호가 남아있다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
• 그 외의 연산자는 출력 큐에 넣는다.

• 입력과 연산자 스택이 모두 비었다면 알고리즘을 종료한다.

상세한 예제

입력: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

연산자	우선순위	연산자 결합 방향
^	4	오른쪽
*	3	왼쪽
/	3	왼쪽
+	2	왼쪽
-	2	왼쪽

입력 토큰	알고리즘의 동작	출력 큐 (역폴란드 표기법)	연산자 스택	비고
3	토큰을 출력 큐에 넣음	3
+	토큰을 연산자 스택에 푸쉬	3	+
4	토큰을 출력 큐에 넣음	3 4	+
*	토큰을 연산자 스택에 푸쉬	3 4	* +	* 의 우선순위가 + 보다 높다
2	토큰을 출력 큐에 넣음	3 4 2	* +
/	연산자 스택에서 팝하여 출력 큐에 넣음	3 4 2 *	+	/ 와 * 의 우선순위는 같다
	토큰을 연산자 스택에 푸쉬	3 4 2 *	/ +	/ 의 우선순위가 + 보다 높다
(	토큰을 연산자 스택에 푸쉬	3 4 2 *	( / +
1	토큰을 출력 큐에 넣음	3 4 2 * 1	( / +
−	토큰을 연산자 스택에 푸쉬	3 4 2 * 1	− ( / +
5	토큰을 출력 큐에 넣음	3 4 2 * 1 5	− ( / +
)	연산자 스택에서 팝하여 출력 큐에 넣음	3 4 2 * 1 5 −	( / +	"("를 찾을 때까지 반복
	스택을 팝함	3 4 2 * 1 5 −	/ +	맞는 괄호를 찾았으므로 괄호를 버림
^	토큰을 연산자 스택에 푸쉬	3 4 2 * 1 5 −	^ / +	^ 의 우선순위가 / 보다 높다
2	토큰을 출력 큐에 넣음	3 4 2 * 1 5 − 2	^ / +
^	토큰을 연산자 스택에 푸쉬	3 4 2 * 1 5 − 2	^ ^ / +	^ 는 오른쪽 결합 연산자이다
3	토큰을 출력 큐에 넣음	3 4 2 * 1 5 − 2 3	^ ^ / +
입력 종료	스택을 팝하여 출력 큐에 넣음	3 4 2 * 1 5 − 2 3 ^ ^ / +

실행 시간 분석

모든 연산자, 괄호 및 숫자는 단 한번만 입력에서 읽고, 최대 한번만 출력 큐에 입력된다. 연산자 및 괄호는 최대 한번만 스택에 푸쉬된 후 팝되므로, 모든 입력 토큰에 대해 최대 몇개의 연산만이 수행된다. 따라서 알고리즘의 실행시간은 입력 길이에 비례하며, 대문자 O 표기법으로는 O(n)이다.