션팅 야드 알고리즘

우리가 쓰는 수식 3 + 4 × 2 를 컴퓨터가 계산하기 쉬운 후위 표기법 3 4 2 × + 로 바꾸는 방법

왜 필요할까? 사람은 연산자를 숫자 사이에 쓰지만(중위 표기법), 컴퓨터는 괄호와 우선순위를 매번 따지기 번거롭습니다. 연산자를 숫자 뒤에 몰아 쓰는 후위 표기법(RPN, Reverse Polish Notation)으로 바꾸면 괄호가 사라지고, 스택 하나로 왼쪽부터 쭉 읽으며 계산할 수 있습니다. 에츠허르 다익스트라가 1961년에 고안한 이 변환법이 션팅 야드(Shunting Yard, 기차 조차장) 알고리즘입니다.

세 가지 표기법

표기법	예시	특징
중위 (infix)	`( 3 + 4 ) × 2`	사람이 읽기 편함 · 괄호와 우선순위 필요
후위 (postfix / RPN)	`3 4 + 2 ×`	괄호 없음 · 스택으로 바로 계산
전위 (prefix)	`× + 3 4 2`	괄호 없음 · 오른쪽부터 계산

연산자 우선순위와 결합 방향

연산자	우선순위	결합 방향
`^` (거듭제곱)	4	오른쪽 (2^3^2 = 2^(3^2))
`×` `÷`	3	왼쪽
`+` `−`	2	왼쪽

직접 돌려보기

입력 토큰 (왼쪽 → 오른쪽으로 읽는 중)

출력 큐 (= 후위식이 여기 쌓임)

연산자 스택 (맨 위 = 왼쪽)

속도

「변환 시작」을 누르면 토큰을 하나씩 읽으며 규칙을 적용합니다.

알고리즘 규칙

토큰을 왼쪽부터 하나씩 읽으며:

숫자 → 바로 출력 큐로 보낸다.
연산자 o1 → 스택 맨 위 연산자 o2 가 (o2 의 우선순위 > o1) 이거나 (우선순위가 같고 o1 이 왼쪽 결합)인 동안, o2 를 꺼내 출력 큐로 보낸다. 그 뒤 o1 을 스택에 넣는다.
여는 괄호 ( → 스택에 넣는다.
닫는 괄호 ) → 여는 괄호를 만날 때까지 스택에서 꺼내 출력한다. 여는 괄호는 버린다.
토큰이 끝나면 → 스택에 남은 연산자를 전부 꺼내 출력한다.

후위식은 스택으로 바로 계산

후위식 3 4 + 2 * 를 왼쪽부터 읽으며: 숫자는 스택에 넣고, 연산자를 만나면 위에서 두 개를 꺼내 계산한 뒤 결과를 다시 넣습니다.

3      → [3]
4      → [3, 4]
+      → 3 + 4 = 7      → [7]
2      → [7, 2]
*      → 7 * 2 = 14     → [14]
결과: 14

의사코드

function toRPN(tokens):
    output = []          # 큐
    ops    = []          # 스택
    for t in tokens:
        if t is number:
            output.push(t)
        else if t is operator o1:
            while ops not empty and top(ops) is operator o2 and
                  (prec(o2) > prec(o1) or
                   (prec(o2) == prec(o1) and o1 is left-assoc)):
                output.push(ops.pop())
            ops.push(o1)
        else if t == '(':
            ops.push(t)
        else if t == ')':
            while top(ops) != '(':
                output.push(ops.pop())
            ops.pop()          # '(' 버림
    while ops not empty:
        output.push(ops.pop())
    return output

어디에 쓰일까? 계산기 앱, 스프레드시트의 수식 엔진, 프로그래밍 언어 컴파일러의 표현식 파서, 데이터베이스의 WHERE 조건 처리 등 "사람이 쓴 수식을 기계가 평가"해야 하는 거의 모든 곳에서 이 아이디어(또는 그 확장인 Pratt 파서)가 쓰입니다.