차량기지 알고리즘

**차량기지 알고리즘**은 중위 표기법으로 표현된 수식을 분석할 때 사용할 수 있는 알고리즘이다. 알고리즘의 결과물은 역폴란드 표기법이나 파스 트리가 될 수 있다. 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라가 고안하여 1961년에 발표하였다. 데이크스트라는 알고리즘의 동작이 철도 차량기지의 그것을 닮았다고 하여 차량기지 알고리즘이라는 이름을 붙였다. 역폴란드 표기법의 계산법처럼, 차량기지 알고리즘 또한 스택을 이용한다. 3+4 또는 3+4 \times (2-1)처럼 대부분의 사람들에게 익숙한 중위 표기법을 역폴란드 표기법으로 변환하려면 입력, 출력 및 한개의 연산자 스택이 필요하다.
# 간단한 예제
그림으로 보는 차량기지 알고리즘. 입력은 한번에 하나씩 들어오며, b), d), f), h) 에서처럼 입력이 변수 또는 숫자일 경우 바로 출력으로 옮겨진다. 만약 입력이 연산자라면, 연산자의 우선순위 및 결합 방향에 따라 c), e)처럼 연산자 스택으로 옮겨지거나, g)처럼 즉시 출력으로 옮겨진다. 입력이 모두 완료되면 연산자 스택의 연산자들이 모두 팝되어 출력으로 옮겨진다. :입력: 3+4 # 첫 번째 입력인 3을 출력 큐로 옮긴다. (숫자가 입력될 때마다 출력으로 옮겨진다) # "+" 연산자를 연산자 스택으로 푸쉬한다. # 4를 출력 큐로 옮긴다. # 입력이 완료되면 연산자 스택에서 연산자들을 팝한 다음 출력으로 옮긴다. # 이 경우 연산자 스택의 연산자는 "+" 한개뿐이다. # 출력: 3 4 + 이 간단한 예제로부터 몇가지 규칙을 살펴볼 수 있다. * 입력이 숫자일 경우 바로 출력으로 옮긴다. * 모든 입력을 읽어들였다면 연산자 스택의 모든 연산자를 팝하여 순서대로 출력으로 옮긴다.
# 자세한 알고리즘
* 입력이 아직 남아있는 동안 :* 입력에서 토큰을 읽어들인다. :* 만약 토큰이 숫자 또는 변수일 경우 출력 큐에 넣는다. :* 만약 토큰이 함수일 경우 연산자 스택에 푸쉬한다. :* 만약 토큰이 함수 인자의 구분자(예: 쉼표)일 경우 ::* 스택에서 여는 괄호 '(' 가 나타날 때까지 팝하여 출력 큐에 넣는다. 만약 여는 괄호가 나타나지 않으면 구분자의 위치가 잘못되었거나 여는 괄호와 닫는 괄호가 맞지 않는 것이므로 오류를 출력한다. :* 토큰이 연산자 o1이라면, 연산자 스택의 맨 위에 연산자가 없을 때까지 다음을 반복한다 ::* 만약 스택에 연산자 o2가 있다면 ::::: o1이 왼쪽 결합 연산자이고, 연산의 우선순위가 o2와 같거나 그보다 낮을 경우, ::::: 또는 o1이 오른쪽 결합 연산자이고, 우선순위가 o2보다 낮을 경우 :::: o2를 팝하여 출력 큐에 넣는다. ::* 만약 스택에 연산자가 없거나 o2가 조건을 만족하지 않으면 o1을 연산자 스택에 푸쉬한다. :* 만약 토큰이 여는 괄호 '(' 일 경우 연산자 스택에 푸쉬한다. :* 만약 토큰이 닫는 괄호 ')' 일 경우 ::* 연산자 스택에서 여는 괄호가 나타날 때까지 연산자를 팝하여 출력 큐에 넣는다. ::* 연산자 스택에서 여는 괄호가 나타나면 팝하되, 출력 큐에는 넣지 않는다. ::* 스택을 모두 팝할 때까지 여는 괄호를 찾지 못했다면 괄호가 맞지 않는 것이므로 오류를 출력한다. ::* 여는 괄호를 팝한 후 스택 맨 위에 함수 토큰이 남아있다면 출력 큐에 넣는다. * 더 이상 입력 토큰이 남아있지 않다면 :* 연산자 스택이 빌 때까지 토큰을 팝한다. ::* 만약 스택에 여는 괄호나 닫는 괄호가 남아있다면 괄호가 맞지 않는 것이므로 오류를 출력한다. ::* 그 외의 연산자는 출력 큐에 넣는다. * 입력과 연산자 스택이 모두 비었다면 알고리즘을 종료한다.
# 상세한 예제
{| 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*)이다. 위키데이터 속성 추적 분류:파싱 알고리즘 분류:에츠허르 데이크스트라