3. 후위 표기식 만들기 : infix-->postfix (스택)

✅ 전체코드

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

a = input()
stack = []
res=''

print(a)

for x in a:
    # 입력값 x 가 숫자라면
    if x.isdecimal():
        res += x
    # x가 숫자가 아니라면면
    else:
        if x == '(':
            stack.append(x)
        elif x=='*' or x =='/':
            while stack and (stack[-1] == '*' or stack[-1] =='/'):
                res += stack.pop()
            stack.append(x)
        elif x =='+' or x=='-':
            while stack and stack[-1] !='(':
                res += stack.pop()
            
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] !='(':
                res+=stack.pop()
            stack.pop()
while stack:
    res += stack.pop()

print(res)

 

 

---

📌 중위 표기법 vs 후위 표기법

중위 표기법후위 표기법

3 + 5	3 5 +
(3 + 5) * 2	3 5 + 2 *
3 + 5 * 2	3 5 2 * +

후위 표기법에서는 괄호 없이도 연산 우선순위를 정확히 표현 가능해!
이 코드는 스택을 사용해 중위 표기법을 후위 표기법으로 변환하는 알고리즘이야.

---

🔍 코드 분석

 

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

• a: 중위 표기법으로 된 수식 입력
• stack: 연산자를 저장하는 스택
• res: 후위 표기법으로 변환된 결과

---

🔢 숫자(0~9)인 경우 → 바로 결과(res)에 추가

 

if x.isdecimal(): res += x

• 숫자는 바로 res에 추가 → 후위 표기법에서는 숫자의 순서는 그대로 유지됨.

---

🔧 연산자(+, -, *, /, (, )) 처리

1️⃣ ( (열린 괄호)

 

elif x == '(': stack.append(x)

• 열린 괄호는 무조건 스택에 push

---

2️⃣ *, / (곱셈, 나눗셈)

elif x == '*' or x == '/': while stack and (stack[-1] == '*' or stack[-1] == '/'): res += stack.pop() stack.append(x)

• *와 /는 같은 우선순위끼리 왼쪽에서 오른쪽으로 연산해야 함
• 스택의 top이 * 또는 /이면 pop해서 res에 추가
• 이후 현재 연산자를 push

---

3️⃣ +, - (덧셈, 뺄셈)

 

elif x == '+' or x == '-': while stack and stack[-1] != '(': res += stack.pop() stack.append(x)

• +, -는 *, /보다 우선순위가 낮음
• 스택에 연산자가 있으면 pop하여 res에 추가
• 이후 현재 연산자를 push

---

4️⃣ ) (닫는 괄호)

elif x == ')': while stack and stack[-1] != '(': res += stack.pop() stack.pop() # 여는 괄호 '(' 제거

• )가 나오면 여는 괄호 (가 나올 때까지 pop해서 res에 추가
• (는 스택에서 제거만 하고 res에 추가하지 않음

---

📌 모든 문자를 확인한 후, 스택에 남은 연산자 정리

 

while stack: res += stack.pop()

• 스택에 남은 연산자들을 차례로 res에 추가
• 이제 후위 표기법으로 변환 완료!

---

💡 실행 예제

입력:

3+(5*2)-8

변환 과정

문자연산스택 상태후위 표기법 (res)

3	숫자 → res 추가	[]	3
+	연산자 → stack 추가	['+']	3
(	연산자 → stack 추가	['+', '(']	3
5	숫자 → res 추가	['+', '(']	3 5
*	연산자 → stack 추가	['+', '(', '*']	3 5
2	숫자 → res 추가	['+', '(', '*']	3 5 2
)	(까지 pop → res 추가	['+']	3 5 2 *
-	+ pop → res 추가, - push	['-']	3 5 2 * +
8	숫자 → res 추가	['-']	3 5 2 * + 8
EOF	스택 pop → res 추가	[]	3 5 2 * + 8 -

출력 결과:

 

3 5 2 * + 8 -

---

⏳ 시간 복잡도 분석

• O(n): 한 번의 문자열 순회(for) + 연산자 처리(while)
• 스택 사용으로 연산자의 우선순위를 효과적으로 관리!

 

---

🚀 정리

✅ 중위 표기법을 후위 표기법으로 변환하는 알고리즘
✅ 스택을 사용해 연산자 우선순위 관리
✅ **시간 복잡도 O(n)**으로 효율적인 연산

이제 후위 표기법으로 변환한 수식을 스택을 이용해 계산할 수도 있어!
이해 안 되는 부분 있으면 질문해줘 😊🔥