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

수학식을 인간이 선호하는 형식인 중위 표기법에서 기계가 효율적으로 처리할 수 있는 형식으로 변환하는 과정은 컴퓨터 과학에서 기본적인 과제입니다. Shunting-Yard 알고리즘은 이 문제에 대한 우아하고 반복적인 해결책을 제공하며, 식을 후위 표기법이라고도 불리는 Reverse Polish Notation(RPN)으로 변환합니다.

이 변환이 중요한 이유는 간단한 스택 기반 머신이 복잡한 역추적이나 괄호의 재귀적 하강 파싱 없이도 한 번의 순방향 패스로 수식의 결과를 계산할 수 있게 해주기 때문입니다.

Shunting-Yard 알고리즘 작동 방식

이 알고리즘은 철도 전환 야적장처럼 동작하며, 토큰(숫자, 연산자, 괄호)을 입력 스트림에서 출력 스트림으로 이동시키고, 스택을 임시 보관 구역(즉, “야적장”)으로 사용합니다.

단계별 과정

Processing Tokens: 알고리즘은 입력에서 토큰을 하나씩 읽습니다.
Operands: 숫자나 변수를 만나면 바로 출력으로 푸시합니다.
Operators: 연산자 $o_1$을 만나면, 알고리즘은 현재 스택 상단에 있는 연산자 $o_2$를 확인합니다. $o_2$의 우선순위가 더 높거나, 우선순위가 같고 $o_1$이 왼쪽 결합법이면, $o_2$를 스택에서 팝하고 출력으로 푸시합니다. 그런 다음 $o_1$을 스택에 푸시합니다.
Parentheses:
- Left Bracket: 스택에 바로 푸시합니다.
- Right Bracket: 왼쪽 괄호가 나올 때까지 스택에서 연산자를 팝하여 출력으로 보냅니다. 이후 왼쪽과 오른쪽 괄호는 모두 버립니다.
Finalization: 모든 입력 토큰을 처리한 후, 스택에 남아 있는 연산자를 모두 출력으로 푸시합니다.

기술적 세부 사항 및 구현상의 도전 과제

Shunting-Yard 알고리즘의 핵심 로직은 간단하지만, 실제 구현에서는 종종 특정 엣지 케이스와 기술적 난관에 직면합니다.

토큰화 및 구분

기본 구현에서 흔히 발생하는 함정은 다자리 숫자를 처리하는 방식입니다. 커뮤니티 구성원들이 지적했듯이, 일부 시연에서는 각 자릿수를 별개의 토큰으로 취급합니다(예: 13을 1, 3으로). 실제 사용 가능한 파서에서는 올바른 렉서가 필요하여 숫자를 하나의 숫자 피연산자로 묶어야 하며, 입력이 100+88/4였을 때 100884+/와 같은 모호한 출력이 발생하지 않도록 합니다.

오류 처리 및 검증

기본적으로 표준 Shunting-Yard 알고리즘은 엄격한 오류 검사를 수행하지 않습니다. 구문적으로 잘못된 입력도 오류를 발생시키지 않고 받아들일 수 있습니다. 그러나 이는 알고리즘 자체의 한계가 아니라 구현 선택에 따른 것입니다. 괄호 불일치나 연속 연산자와 같은 검증 로직을 추가하는 것은 견고한 식 평가기를 구축하기 위한 필수 단계입니다.

다른 파싱 기법과의 관계

기술적으로 Shunting-Yard 알고리즘은 재귀 파싱 방식에 대한 반복적인 대안으로 볼 수 있습니다. 이는 연산자 우선순위와 결합법을 더 복잡한 언어 문법에서 처리하기 위해 사용되는 Pratt parsing 및 precedence climbing과 밀접한 관련이 있습니다.

이론적 관점

파싱의 실용적인 적용을 넘어, 이 알고리즘은 흥미로운 이론적 질문을 제기합니다. 일부 관찰자는 표준 계산과 reversible computing 사이의 차이를 지적했는데, 여기서 계산의 “쓰레기”(예: 버려진 괄호)는 단순히 삭제될 수 없으며, 과정을 역전시키기 위해 보존되어야 합니다.

궁극적으로 Shunting-Yard 알고리즘은 컴파일러 설계와 식 평가의 핵심 요소로 남아 있으며, 인간이 읽을 수 있는 수학 표기법과 스택 기반의 기계 실행 로직 사이의 간극을 메워줍니다.