차량기지 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

간단한 예제[편집]

그림으로 보는 차량기지 알고리즘. 입력은 한번에 하나씩 들어오며, b), d), f), h) 에서처럼 입력이 변수 또는 숫자일 경우 바로 출력으로 옮겨진다. 만약 입력이 연산자라면, 연산자의 우선순위 및 결합 방향에 따라 c), e) 처럼 연산자 스택으로 옮겨지거나, g) 처럼 즉시 출력으로 옮겨진다. 입력이 모두 완료되면 연산자 스택의 연산자들이 모두 팝되어 출력으로 옮겨진다.
입력: 3+4
  1. 첫 번째 입력인 3을 출력 로 옮긴다. (숫자가 입력될 때마다 출력으로 옮겨진다)
  2. "+" 연산자를 연산자 스택으로 푸쉬한다.
  3. 4를 출력 큐로 옮긴다.
  4. 입력이 완료되면 연산자 스택에서 연산자들을 팝한 다음 출력으로 옮긴다.
  5. 이 경우 연산자 스택의 연산자는 "+" 한개뿐이다.
  6. 출력: 3 4 +

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

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

자세한 알고리즘[편집]

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

상세한 예제[편집]

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

실행 시간 분석[편집]

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