1. 후위 표기식이란?
후위 표기식은 연산자를 피연산자 뒤에 쓰는 표현 방법입니다. 영어로는 Postfix Expression 또는 Reverse Polish Notation, RPN이라고 합니다.
| 표현 방식 | 예 | 의미 |
|---|---|---|
| 중위 표기식 | 2 + 3 | 연산자가 두 수의 가운데에 위치 |
| 후위 표기식 | 2 3 + | 연산자가 두 수의 뒤에 위치 |
예를 들어 중위식 (2 + 3) * 4는 후위식으로 2 3 + 4 *가 됩니다.
숫자를 만나면 스택에 넣고, 연산자를 만나면 스택에서 숫자 두 개를 꺼내 계산한 뒤 그 결과를 다시 스택에 넣습니다.
2. 전체 파이썬 코드
def postfix(tokens):
stack = []
for token in tokens:
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
elif token == "/":
stack.append(a / b)
return stack.pop()
print(postfix(["2", "3", "+"]))
print(postfix(["5", "2", "*"]))
print(postfix(["2", "3", "+", "4", "*"]))
print(postfix(["2", "3", "4", "*", "+"]))
print(postfix(["2", "3", "+", "4", "5", "+", "*"]))
print(postfix(["8", "2", "-", "3", "*"]))
print(postfix(["8", "2", "/", "3", "+"]))
print(postfix(["10", "2", "3", "*", "+"]))
print(postfix(["10", "2", "+", "3", "4", "+", "*"]))
print(postfix(["2", "3", "+", "4", "5", "+", "*", "6", "+"]))2-1. def postfix(tokens):
postfix라는 함수를 정의합니다. tokens는 후위 표기식을 구성하는 숫자와 연산자를 담은 리스트입니다.
예: ["2", "3", "+"]
2-2. stack = []
빈 리스트를 만들고 이 리스트를 스택처럼 사용합니다. 스택은 나중에 들어간 자료가 먼저 나오는 LIFO 구조입니다.
2-3. for token in tokens:
리스트의 요소를 왼쪽부터 하나씩 꺼냅니다. ["2", "3", "+"]라면 token은 차례대로 "2", "3", "+"가 됩니다.
2-4. if token.isdigit():
isdigit()은 문자열이 숫자로만 이루어졌는지 검사합니다.
| 표현 | 결과 |
|---|---|
"2".isdigit() | True |
"10".isdigit() | True |
"+".isdigit() | False |
"*".isdigit() | False |
2-5. stack.append(int(token))
숫자 문자열을 int()로 정수로 변환한 뒤 스택의 맨 뒤에 넣습니다.
token = "3"
int(token) # 3
stack.append(3) # 스택에 3 저장2-6. 숫자가 아니면 연산자로 처리
else:
b = stack.pop()
a = stack.pop()pop()은 리스트의 마지막 요소를 꺼내면서 삭제합니다. 먼저 꺼낸 값은 b, 두 번째로 꺼낸 값은 a가 됩니다.
8 2 -에서 먼저 꺼낸 값은 b = 2, 다음 값은 a = 8입니다. 따라서 계산은 a - b, 즉 8 - 2입니다.
2-7. 연산 종류 판단
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
elif token == "/":
stack.append(a / b)연산자에 맞게 계산하고 그 결과를 다시 스택에 넣습니다.
2-8. return stack.pop()
모든 토큰을 처리한 뒤 스택에 남은 최종 결과 하나를 꺼내 반환합니다. 올바른 후위식이라면 마지막에 스택에는 값이 정확히 하나만 남아야 합니다.
3. 실행 과정을 직접 추적해 보기
예제 A: 2 3 +
| token | 동작 | stack |
|---|---|---|
| 2 | 숫자이므로 push | [2] |
| 3 | 숫자이므로 push | [2, 3] |
| + | 3과 2를 pop → 2+3=5 → push | [5] |
최종 결과: 5
예제 B: 2 3 + 4 *
| token | 동작 | stack |
|---|---|---|
| 2 | push | [2] |
| 3 | push | [2, 3] |
| + | 2+3=5 | [5] |
| 4 | push | [5, 4] |
| * | 5×4=20 | [20] |
중위식은 (2 + 3) * 4, 결과는 20입니다.
예제 C: 2 3 4 * +
| token | 동작 | stack |
|---|---|---|
| 2 | push | [2] |
| 3 | push | [2, 3] |
| 4 | push | [2, 3, 4] |
| * | 3×4=12 | [2, 12] |
| + | 2+12=14 | [14] |
중위식은 2 + (3 * 4), 결과는 14입니다.
예제 D: 2 3 + 4 5 + *
| token | 동작 | stack |
|---|---|---|
| 2 | push | [2] |
| 3 | push | [2, 3] |
| + | 2+3=5 | [5] |
| 4 | push | [5, 4] |
| 5 | push | [5, 4, 5] |
| + | 4+5=9 | [5, 9] |
| * | 5×9=45 | [45] |
중위식은 (2 + 3) * (4 + 5), 결과는 45입니다.
4. 올바른 후위 표기식의 조건
이 코드처럼 모든 연산자가 두 개의 피연산자를 필요로 하는 이항 연산자라고 가정하면 다음 두 조건이 가장 중요합니다.
| 조건 | 설명 |
|---|---|
| ① 연산자를 만났을 때 스택에 숫자가 2개 이상 있어야 한다. | 2 +처럼 숫자가 하나밖에 없으면 잘못된 식입니다. |
| ② 모든 계산이 끝난 뒤 스택에 값이 정확히 1개 남아야 한다. | 2 3 4 +는 계산 후 값이 두 개 남으므로 완전한 하나의 식이 아닙니다. |
또한 이항 연산자만 있다면 전체적으로 피연산자 수 = 연산자 수 + 1이어야 합니다.
5. 중위식과 후위식 비교
| 중위식 | 후위식 | 결과 |
|---|---|---|
2 + 3 | 2 3 + | 5 |
(2 + 3) * 4 | 2 3 + 4 * | 20 |
2 + (3 * 4) | 2 3 4 * + | 14 |
(8 - 2) * 3 | 8 2 - 3 * | 18 |
(8 / 2) + 3 | 8 2 / 3 + | 7 |
6. 응시자 정보
7. 단답형 계산 문제 10개
각 후위 표기식의 계산 결과를 입력하세요. 각 문항은 10점, 총 100점입니다.
8. 학습 정리
① 숫자를 만나면 스택에 넣는다.
② 연산자를 만나면 두 값을 꺼내
a 연산 b를 계산한다.③ 계산 결과를 다시 스택에 넣는다.
후위 표기식은 괄호가 없어도 계산 순서가 명확하다는 장점이 있습니다. 그래서 스택의 대표적인 활용 예제로 자주 사용됩니다.