차량기지 알고리즘
From Wikipedia, the free encyclopedia
차량기지 알고리즘은 중위 표기법으로 표현된 수식을 분석할 때 사용할 수 있는 알고리즘이다. 알고리즘의 결과물은 역폴란드 표기법이나 파스 트리가 될 수 있다. 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라가 고안하여 1961년에 발표하였다. 데이크스트라는 알고리즘의 동작이 철도 차량기지의 그것을 닮았다고 하여 차량기지 알고리즘이라는 이름을 붙였다.
역폴란드 표기법의 계산법처럼, 차량기지 알고리즘 또한 스택을 이용한다. 또는 처럼 대부분의 사람들에게 익숙한 중위 표기법을 역폴란드 표기법으로 변환하려면 입력, 출력 및 한개의 연산자 스택이 필요하다.