션팅 야드 알고리즘

션팅 알고리즘(Shunting Yard Algorithm)은 중위 표기법(infix notation) 수식을 후위 표기법(postfix notation)으로 변환하는 알고리즘이다.

중위 표기법은 일반적으로 우리가 일상적으로 사용하는 수식 표기법이다. 예를 들어, "3 + 4 * 2 / (1 - 5)^2"와 같은 형태를 갖는다. 하지만, 컴퓨터가 수식을 계산하는 경우에는 후위 표기법을 사용하는 것이 효율적이다.

션팅 알고리즘은 다음과 같은 절차로 수식을 후위 표기법으로 변환한다.

1. 수식의 각 토큰(숫자 및 연산자)을 순차적으로 읽는다.
2. 토큰이 숫자인 경우, 출력 큐(output queue)에 추가한다.
3. 토큰이 연산자인 경우, 연산자 스택(operator stack)에 추가한다.
4. 연산자를 추가하기 전에, 스택의 맨 위에 있는 연산자의 우선순위와 현재 읽은 연산자의 우선순위를 비교한다. 우선순위가 같거나 높으면, 스택에서 연산자를 꺼내 출력 큐에 추가한다.
5. 닫는 괄호를 만나면, 스택에서 여는 괄호를 만날 때까지 연산자를 꺼내 출력 큐에 추가한다.
6. 모든 토큰을 다 읽으면, 연산자 스택에 남아있는 모든 연산자를 출력 큐에 추가한다.

이후 출력 큐의 토큰을 순서대로 읽어, 후위 표기법으로 계산할 수 있다.