전위(Prefix), 중위(Infix), 후위(Postfix) 표기법
전위(Prefix), 후위(Postfix) 연산자의 차이 포스팅을 함께 참고하시면 좋습니다.
수식을 표현하는 방법에는 연산자의 위치에 따라 전위(Prefix), 중위(Infix), 후위(Postfix) 표기법이 있습니다.
우리가 일상에 사용하는 3 + 5는 중위 표기법이지만, 컴퓨터가 수식을 처리할 때는 전위/후위 표기법이 더 효율적입니다.
이번 포스팅에서는 세 가지 표기법의 개념과 차이, 그리고 컴퓨터가 수식을 계산하는 방식을 정리해보겠습니다.
1. 세 가지 표기법 비교
수식에서 연산자가 어디에 위치하느냐에 따라 표기법이 구분됩니다.
| 표기법 | 방식 | 예시 |
|---|---|---|
| Infix (중위) | 연산자가 피연산자 사이에 위치 | 3 + 5 |
| Prefix (전위) | 연산자가 피연산자 앞에 위치 | + 3 5 |
| Postfix (후위) | 연산자가 피연산자 뒤에 위치 | 3 5 + |
2. 중위 표기법 (Infix Notation)
중위 표기법은 우리가 일상 생활에 사용하는 가장 익숙한 표기 방식입니다.
연산자가 두 피연산자 사이에 위치하며, 사람이 읽고 쓰기에 직관적입니다.
1
2
3 + 5
(3 + 5) * 2
하지만 중위 표기법에는 연산자 우선순위와 괄호에 의존해야 한다는 단점이 있습니다.
예를 들어 3 + 5 * 2는 괄호 없이는 *가 먼저 계산되어 13이 되지만, (3 + 5) * 2로 감싸면 16이 됩니다.
이처럼 중위 표기법은 괄호와 우선순위 규칙에 의존하기 때문에, 컴퓨터가 직접 처리하기에는 비효율적입니다.
이러한 한계를 해결하기 위해 등장한 것이 전위(Prefix)와 후위(Postfix) 표기법입니다.
3. 전위 표기법 (Prefix Notation)
전위 표기법은 폴란드 표기법(Polish Notation)이라고도 불립니다.
연산자가 피연산자보다 앞에 오며, 괄호 없이도 연산 순서를 명확하게 표현할 수 있다는 특징이 있습니다.
중위 표기법 (3 + 5) * 2를 전위 표기법으로 변환하는 과정은 다음과 같습니다.
1
2
3
4
5
(3 + 5) * 2
A. 가장 안쪽 괄호부터 변환: (3 + 5) → + 3 5
B. 전체 수식에 대입: (+ 3 5) * 2
C. 바깥 연산자를 앞으로: * + 3 5 2
변환된 전위 표기법의 계산 과정은 다음과 같습니다.
1
2
3
4
5
6
7
* + 3 5 2
A. 가장 안쪽의 연산자 + 를 찾음 → 피연산자 3, 5
B. + 3 5 → 3+5=8
C. * 8 2 → 8*2=16
결과: 16
4. 후위 표기법 (Postfix Notation)
후위 표기법은 역폴란드 표기법(Reverse Polish Notation)이라고도 불립니다.
연산자가 피연산자보다 뒤에 오며, 컴퓨터가 스택(Stack) 자료구조를 활용하여 수식을 계산하기에 매우 적합한 방식입니다.
중위 표기법 (3 + 5) * 2를 후위 표기법으로 변환하는 과정은 다음과 같습니다.
1
2
3
4
5
(3 + 5) * 2
A. 가장 안쪽 괄호부터 변환: (3 + 5) → 3 5 +
B. 전체 수식에 대입: (3 5 +) * 2
C. 바깥 연산자를 뒤로: 3 5 + 2 *
후위 표기법은 컴파일러와 계산기 내부 구현에 실제로 활용되며, 스택을 이용한 계산 과정은 다음과 같습니다.
1
2
3
4
5
6
7
8
9
3 5 + 2 *
A. 3 → 스택에 push: [3]
B. 5 → 스택에 push: [3, 5]
C. + → 스택에서 5, 3을 pop → 3+5=8 → 스택에 push: [8]
D. 2 → 스택에 push: [8, 2]
E. * → 스택에서 2, 8을 pop → 8*2=16 → 스택에 push: [16]
결과: 16
5. 전위/후위 표기법이 컴퓨터에 유리한 이유
중위 표기법은 괄호와 연산자 우선순위를 파싱해야 합니다.
하지만, 전위/후위 표기법은 괄호 없이도 연산 순서가 명확하여 컴퓨터가 훨씬 효율적으로 처리할 수 있습니다.
| Infix (중위) | Prefix (전위) | Postfix (후위) | |
|---|---|---|---|
| 괄호 | 필요 | 불필요 | 불필요 |
| 우선순위 규칙 | 필요 | 불필요 | 불필요 |
| 계산 방식 | 파싱 트리 필요 | 재귀적 처리 | 스택 하나로 처리 |
| 사용처 | 사람이 읽는 수식 | 함수형 언어 (Lisp 등) | 컴파일러, 계산기 내부 |
이 중 후위 표기법은 왼쪽에서 오른쪽으로 순서대로 읽으며 스택에 넣고 빼기만 하면 계산이 완료되기 때문에, 대부분의 컴파일러는 중위 표기법으로 작성된 수식을 후위 표기법으로 변환한 뒤 계산을 수행합니다.