차량기지 알고리즘 문서 원본 보기

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

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

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

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

이 간단한 예제로부터 몇가지 규칙을 살펴볼 수 있다.
* 입력이 숫자일 경우 바로 출력으로 옮긴다.
* 모든 입력을 읽어들였다면 연산자 스택의 모든 연산자를 팝하여 순서대로 출력으로 옮긴다.

== 자세한 알고리즘 ==
* 입력이 아직 남아있는 동안
:* 입력에서 [[낱말 분석|토큰]]을 읽어들인다.
:* 만약 토큰이 숫자 또는 변수일 경우 출력 큐에 넣는다.
:* 만약 토큰이 함수일 경우 연산자 스택에 푸쉬한다.
:* 만약 토큰이 함수 인자의 구분자(예: 쉼표)일 경우
::* 스택에서 여는 괄호 '(' 가 나타날 때까지 팝하여 출력 큐에 넣는다. 만약 여는 괄호가 나타나지 않으면 구분자의 위치가 잘못되었거나 여는 괄호와 닫는 괄호가 맞지 않는 것이므로 오류를 출력한다.
:* 토큰이 연산자 o<sub>1</sub>이라면, 연산자 스택의 맨 위에 연산자가 없을 때까지 다음을 반복한다
::* 만약 스택에 연산자 o<sub>2</sub>가 있다면
::::: o<sub>1</sub>이 왼쪽 결합 연산자이고, [[연산의 우선순위]]가 o<sub>2</sub>와 같거나 그보다 낮을 경우,
::::: 또는 o<sub>1</sub>이 오른쪽 결합 연산자이고, 우선순위가 o<sub>2</sub>보다 낮을 경우
:::: o<sub>2</sub>를 팝하여 출력 큐에 넣는다.
::* 만약 스택에 연산자가 없거나 o<sub>2</sub>가 조건을 만족하지 않으면 o<sub>1</sub>을 연산자 스택에 푸쉬한다.
:* 만약 토큰이 여는 괄호 '(' 일 경우 연산자 스택에 푸쉬한다.
:* 만약 토큰이 닫는 괄호 ')' 일 경우
::* 연산자 스택에서 여는 괄호가 나타날 때까지 연산자를 팝하여 출력 큐에 넣는다.
::* 연산자 스택에서 여는 괄호가 나타나면 팝하되, 출력 큐에는 넣지 않는다.
::* 스택을 모두 팝할 때까지 여는 괄호를 찾지 못했다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
::* 여는 괄호를 팝한 후 스택 맨 위에 함수 토큰이 남아있다면 출력 큐에 넣는다.
* 더 이상 입력 토큰이 남아있지 않다면
:* 연산자 스택이 빌 때까지 토큰을 팝한다.
::* 만약 스택에 여는 괄호나 닫는 괄호가 남아있다면 괄호가 맞지 않는 것이므로 오류를 출력한다.
::* 그 외의 연산자는 출력 큐에 넣는다.
* 입력과 연산자 스택이 모두 비었다면 알고리즘을 종료한다.

== 상세한 예제 ==
{| class="wikitable"
|+ 입력:   3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

! 연산자 !! 우선순위 !! 연산자 결합 방향
|- || align="center"
| ^ || 4 || 오른쪽
|- || align="center"
| * || 3 || 왼쪽
|- || align="center"
| / || 3 || 왼쪽
|- || align="center"
| + || 2 || 왼쪽
|- || align="center"
| - || 2 || 왼쪽
|}

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

== 실행 시간 분석 ==

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

[[분류:파싱 알고리즘]]
[[분류:에츠허르 데이크스트라]]