차량기지 알고리즘(Shunting Yard Algorithm)은 중위 표기법(infix notation)으로 표현된 수식을 분석하여 후위 표기법(postfix notation, 역폴란드 표기법) 또는 파스 트리(parse tree)로 변환하는 데 사용되는 알고리즘이다. 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라(Edsger Dijkstra)가 고안하여 1961년에 발표하였다.
명칭의 유래
"차량기지"라는 이름은 철도 차량기지(shunting yard)에서 열차 칸들을 일시적으로 대피시켰다가 목적에 맞게 재배치하는 방식에서 착안한 것이다. 이 알고리즘에서 연산자를 스택에 임시로 저장해 두었다가 적절한 시점에 꺼내 출력하는 과정이, 철도 기지에서 차량을 분리하고 재조립하는 과정과 유사하여 이와 같은 이름이 붙었다. 영문 원어인 "Shunting Yard"는 철도 차량의 분류·조성 작업장을 의미한다.
주요 원리
이 알고리즘은 입력 수식을 왼쪽에서 오른쪽으로 읽어 나가며, 다음과 같은 규칙에 따라 토큰을 처리한다.
- 피연산자(숫자 등)는 즉시 출력 큐에 넣는다.
- 연산자는 연산자 스택에 삽입하되, 스택 상단에 이미 존재하는 연산자의 우선순위가 현재 연산자의 우선순위보다 같거나 높으면 해당 연산자들을 먼저 출력 큐로 이동시킨 뒤 현재 연산자를 스택에 삽입한다.
- 열린 괄호는 스택에 삽입하고, 닫힌 괄호를 만나면 열린 괄호가 나올 때까지 스택의 연산자를 모두 출력한다.
- 입력을 모두 처리한 뒤에는 스택에 남은 연산자를 순서대로 출력한다.
이 과정을 통해 연산자의 우선순위와 결합 법칙이 이미 반영된 후위 표기법 수식이 생성된다.
활용 분야
차량기지 알고리즘은 컴파일러의 수식 파싱, 계산기 프로그램, 수식 계산 기능을 갖는 다양한 소프트웨어에서 널리 활용된다. 후위 표기법으로 변환된 수식은 괄호나 우선순위에 대한 별도의 고려 없이 스택만으로 순차적으로 계산할 수 있다는 장점이 있어, 프로그래밍 언어의 표현식 평가나 수식 트리 구축 등에 효과적으로 사용된다.
참고 사항
이 단어는 철도 운영과 관련된 "차량기지"라는 일반명사와 혼동될 수 있으나, 컴퓨터과학 분야에서 "차량기지 알고리즘"은 위에서 설명한 Shunting Yard Algorithm을 가리키는 표준 용어로, 위키백과를 비롯한 여러 공신력 있는 자료에서 별도 문서로 다루어지고 있다.
