Shunting Yard 알고리즘: 중위 표기법에서 후위 표기법으로

1. 개요

Shunting Yard 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라가 고안한 알고리즘으로, 중위 표기법으로 표현된 수식을 후위 표기법으로 변환하는 데 사용된다. 이 알고리즘은 계산기나 컴파일러에서 널리 사용되며, 수식의 연산자 우선순위를 고려해 쉽게 계산할 수 있는 후위 표기법으로 변환하는 것이 핵심이다.

이 문서에서는 Shunting Yard 알고리즘의 원리, Python 구현 방법, 그리고 다양한 응용 사례를 설명한다.

2. Shunting Yard 알고리즘이란?

Shunting Yard 알고리즘은 스택을 기반으로 중위 표기법을 후위 표기법으로 변환하는 알고리즘이다.

• 중위 표기법 (Infix Notation)
  • 연산자가 피연산자 사이에 위치 (예: 3 + 4 * 2)
• 후위 표기법 (Postfix Notation)
  • 연산자가 피연산자 뒤에 위치 (예: 3 4 2 * +)

후위 표기법으로 변환된 수식은 스택을 이용해 쉽게 계산할 수 있다.

3. Shunting Yard 알고리즘의 동작 원리

Shunting Yard 알고리즘은 다음과 같은 규칙을 따른다.

1. 피연산자
   • 출력 큐에 삽입한다.
2. 연산자
   • 스택에서 우선순위에 따라 처리한 후 출력 큐로 이동한다.
3. 괄호
   • 여는 괄호 (: 스택에 푸쉬한다.
   • 닫는 괄호 ):
     • 스택에서 여는 괄호가 나타날 때까지 연산자를 팝해 출력 큐로 이동한다.
     • 여는 괄호는 제거하고 출력 큐에는 넣지 않는다.

입력이 끝난 후에는 스택에 남아 있는 연산자를 모두 출력 큐로 이동시킨다.

3.1. 알고리즘 단계

1. 입력에서 토큰을 읽는다.
2. 토큰의 종류에 따라 다음을 수행:
   • 숫자/변수: 출력 큐에 삽입.
   • 연산자:
     • 스택에 연산자가 있고, 현재 연산자가 스택 최상위 연산자보다 우선순위가 낮거나 같으면 팝하여 출력 큐에 삽입.
     • 연산자를 스택에 푸쉬.
   • 여는 괄호: 스택에 푸쉬.
   • 닫는 괄호:
     • 스택에서 여는 괄호가 나타날 때까지 연산자를 팝하여 출력 큐에 삽입.
     • 여는 괄호 제거.
3. 입력이 끝나면 스택에 남아 있는 연산자를 모두 팝하여 출력 큐에 삽입.

3.2. 예시 1: A + B × C - D

입력 토큰	출력 큐	연산자 스택
A	A
+	A	+
B	A B	+
*	A B	+ *
C	A B C	+ *
-	A B C * +	-
D	A B C * + D	-

결과: A B C × + D -

3.3. 예시 2: 3 + 4 × 2 / ( 1 - 5 ) ^ 2 ^ 3

입력 토큰	출력 큐	연산자 스택	비고
3	3		숫자 출력
+	3	+	연산자 스택에 푸쉬
4	3 4	+	숫자 출력
*	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 -	+ / ^	^는 우선순위 높음
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 ^ ^ / +		모든 연산자 팝

결과: 3 4 2 × 1 5 - 2 3 ^ ^ / +

4. Python 구현

def shunting_yard(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    output = []
    operators = []

    for token in expression:
        if token.isdigit():
            output.append(token)
        elif token in precedence:
            while operators and operators[-1] != '(' and precedence[operators[-1]] >= precedence[token]:
                output.append(operators.pop())
            operators.append(token)
        elif token == '(':
            operators.append(token)
        elif token == ')':
            while operators and operators[-1] != '(':
                output.append(operators.pop())
            operators.pop()

    while operators:
        output.append(operators.pop())

    return ' '.join(output)

expression = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3".split()
print(shunting_yard(expression))

출력: 3 4 2 * 1 5 - 2 3 ^ ^ / +

5. Shunting Yard 알고리즘의 장단점

장점:

• 연산자 우선순위와 괄호 처리를 효율적으로 수행한다.
• 중위 표기법을 후위 표기법으로 빠르게 변환한다.
• 컴파일러와 계산기에서 응용 가능하다.

단점:

• 복잡한 우선순위와 괄호 구조는 코드 복잡성을 증가시킬 수 있다.
• 언어별 연산자 우선순위 정의가 필요하다.

6. Shunting Yard 알고리즘의 응용

• 계산기 구현
  • 후위 표기법을 사용해 수식을 계산한다.
• 컴파일러
  • 수식 파싱 및 분석한다.
• 수식 평가 엔진
  • 복잡한 수식을 처리한다.

7. 결론

Shunting Yard 알고리즘은 중위 표기법을 후위 표기법으로 변환하는 강력한 도구로, 연산자 우선순위와 괄호 처리를 효과적으로 수행한다. Python과 같은 언어로 간단히 구현 가능하며, 계산기, 컴파일러, 데이터베이스 등 다양한 분야에 활용할 수 있다.