폴란드 표기법 변환기 (중위 ↔ 전위·후위/역폴란드 표기)

폴란드 표기법 변환기 쉽게 이해하기 — 개념과 원리

이 변환기는 산술식을 중위 표기(보통 쓰는 형태), 전위 표기(폴란드 표기), 후위 표기(역폴란드 표기) 사이에서 바꾸고, 값을 계산하며, 스택이 수행하는 순서대로 연산을 나열합니다. 컴퓨터과학 수업, 컴파일러나 계산기 프로그래밍, RPN 계산기 사용, 연산 순서 확인에 씁니다.

계산 방법

• 중위식은 보통의 우선순위로 해석합니다. ^가 먼저(오른쪽부터), 다음 ×와 ÷, 그다음 +와 −(왼쪽부터)입니다. 숫자 바로 앞의 −는 음수로 읽습니다.
• 후위 표기는 연산자를 두 피연산자 뒤에, 전위 표기는 앞에 씁니다.
• 계산은 스택으로 합니다. 후위식을 왼쪽부터 읽으며 수는 쌓고, 연산자를 만나면 두 값을 꺼내(먼저 꺼낸 값이 오른쪽 피연산자) 계산한 뒤 다시 쌓습니다. 전위식은 오른쪽부터 같은 방식으로 읽습니다.
• 중위식 결과에는 꼭 필요한 괄호만 씁니다.

원리

중위 표기는 무엇을 먼저 계산할지 정하려면 우선순위 규칙과 괄호가 필요합니다. 얀 우카시에비치는 모든 연산자를 피연산자 앞에 두면 괄호가 전혀 필요 없음을 보였습니다. 각 연산자가 항상 뒤따르는 완전한 식 두 개를 받기 때문입니다. 후위 표기는 연산자를 뒤에 두는 같은 방식으로, 수가 스택에서 기다리다가 연산자가 쓰는 스택 기계의 동작과 정확히 맞습니다. 그래서 많은 컴파일러가 식을 후위 표기로 바꾸고, 일부 계산기는 RPN 방식을 씁니다.

예제 풀이

기본 입력은 중위식 (3 + 4) × 5 − 6 ÷ 2입니다.

1. 전위 표기: − × + 3 4 5 ÷ 6 2
2. 후위 표기: 3 4 + 5 × 6 2 ÷ −
3. 스택 계산: 3 + 4 = 7, 7 × 5 = 35, 6 ÷ 2 = 3, 35 − 3 = 32
4. 값은 32이고 연산자는 4개입니다.

결과 해석

전위식은 '이 연산자를 다음 두 덩어리에 적용한다'로 읽습니다. 즉 − (× (+ 3 4) 5) (÷ 6 2)입니다. 연산 목록은 컴퓨터가 식을 계산하는 정확한 순서를 보여 줍니다. 값이 예상과 다르면 입력한 중위식의 우선순위가 의도와 다를 가능성이 큽니다. 직접 변환을 연습할 때는 계산기 결과와 한 단계씩 비교해 보면 스택 동작이 잘 이해됩니다.

흔한 실수

• 스택에서 꺼낼 때 −나 ÷의 피연산자 순서를 뒤집는 경우(먼저 꺼낸 값이 오른쪽입니다)
• 2 ^ 3 ^ 2를 (2 ^ 3) ^ 2로 계산하는 경우(오른쪽부터 묶어 2 ^ 9 = 512입니다)
• 후위식에서 여러 자리 수 사이에 공백을 빼 3 4가 34가 되는 경우
• 음수 부호와 뺄셈 연산자를 혼동하는 경우

자주 묻는 질문

왜 폴란드 표기법이라고 하나요?

폴란드의 논리학자 얀 우카시에비치가 1920년대에 고안했기 때문입니다.

후위 표기에도 괄호가 필요한가요?

아닙니다. 기호의 순서만으로 연산 순서가 정해집니다.

전위식은 후위식을 거꾸로 쓴 것인가요?

일반적으로는 아닙니다. 거꾸로 쓰면 피연산자 순서까지 바뀌기 때문입니다.

출처: Weisstein, E. W., "Reverse Polish Notation", Wolfram MathWorld