4. 후위연산(stack)_파이썬

🚀전체 코드

import sys
sys.stdin=open("C:\\input.txt",'rt')

a = input()
print(a)

stack = []
res = ''

for x in a:
    # x가 숫자일 경우
    if x.isdecimal():
        stack.append(int(x))
    # x가 숫자가 아닐 경우
    else:
        if x =='+':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2+n1)
        elif x =='-':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2-n1)
        elif x == '*':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2*n1)
        elif x == '/':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2/n1)
print(stack[0])

 

 

---

📌 후위 표기법 계산법

후위 표기법에서는 연산자가 뒤에 위치하기 때문에,
왼쪽에서 오른쪽으로 읽으면서 숫자는 스택에 넣고, 연산자는 꺼내서 계산하면 돼.

📝 후위 표기법 예제

복사편집

3 5 2 * + 8 -

→ 계산 순서:

1. 3 → 스택에 push
2. 5 → 스택에 push
3. 2 → 스택에 push
4. * → 5 * 2 = 10, 결과를 스택에 push
5. + → 3 + 10 = 13, 결과를 스택에 push
6. 8 → 스택에 push
7. - → 13 - 8 = 5, 결과를 스택에 push
   ➡ 최종 결과 = 5

---

🔍 코드 분석

import sys sys.stdin = open("C:\\Users\\csh\\Documents\\코딩테스트\\자료구조활용(스택,큐,해쉬,힙)\\input.txt", 'rt') a = input() # 후위 표기법 수식 입력 print(a) stack = [] # 숫자를 저장할 스택

 

• a: 후위 표기법 수식 (공백 없이 입력)
• stack: 숫자 저장을 위한 스택

---

🔢 숫자인 경우 → 스택에 push

if x.isdecimal(): stack.append(int(x))

 

• isdecimal() → 숫자인지 확인
• 숫자면 정수형으로 변환해서 스택에 push

---

➕➖ 곱셈/나눗셈 처리

else: if x == '+': n1 = stack.pop() n2 = stack.pop() stack.append(n2 + n1) elif x == '-': n1 = stack.pop() n2 = stack.pop() stack.append(n2 - n1) elif x == '*': n1 = stack.pop() n2 = stack.pop() stack.append(n2 * n1) elif x == '/': n1 = stack.pop() n2 = stack.pop() stack.append(n2 / n1)

• 연산자가 나오면 스택에서 두 개의 숫자를 꺼냄
• n2가 먼저 pop() → 연산의 왼쪽 숫자
• n1이 다음 pop() → 연산의 오른쪽 숫자
• 계산 후 결과를 다시 스택에 push

---

✅ 최종 결과 출력

print(stack[0])

• 스택의 마지막 값이 정답이므로 출력

---

💡 실행 예제

입력

352*+8-

계산 과정 (스택 상태)

문자연산스택 상태

3	push	[3]
5	push	[3, 5]
2	push	[3, 5, 2]
*	5 * 2 = 10 → push	[3, 10]
+	3 + 10 = 13 → push	[13]
8	push	[13, 8]
-	13 - 8 = 5 → push	[5]

출력 결과

5

---

⏳ 시간 복잡도 분석

• O(n) → 후위 표기법 수식을 한 번만 순회하면서 연산
• 스택 연산(push, pop) → O(1) 이므로 전체적으로 매우 빠름

---

🔹 정리

✅ 후위 표기법 수식을 스택을 사용해 계산
✅ 연산자를 만나면 숫자 두 개를 꺼내서 계산 후 다시 push
✅ 시간 복잡도 O(n), 매우 효율적