차량기지 알고리즘

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

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

입력: 3+4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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