[백준] 후위 표기식 1918번 파이썬 Python 자료구조

📌생각해보기

중위 표기식(A+B*C-D/E)을 후위 표기식(ABC*+DE/-)으로 바꿔야한다.

주어진 자료를 재정리 해야한다.
Stack은 주어진 자료를 재정리 할 때 주로 사용되는 방법이다.

1. 알파벳은 문자열로 쌓고
2. 괄호와 연산자는 Stack에 쌓는다.
3. 조건이 맞으면 Stack에 있는 연산자를 문자열에 쌓는다.

📌내가 작성한 코드

num = input()
answer = ''
stack = []

for i in num:
    if i.isalpha():
        answer += i
    else:
        if i == '(':
            stack.append(i)
            
        elif i == '*' or i == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                answer += stack.pop()
            stack.append(i)
            
        elif i == '+' or i == '-':
            while stack and stack[-1] != '(':
                answer += stack.pop()
            stack.append(i)
            
        elif i == ')':
            while stack and stack[-1] != '(':
                answer += stack.pop()
            stack.pop()

while stack:
    answer += stack.pop()

print(answer)

📌풀이

1. 받은 input 값 중 알파벳이 있으면 answer에 쌓는다.

if i.isalpha():
	answer += i

2. 알파벳이 아니고 i가 ( 일 때, 스택에 쌓는다.

if i == '(':
	stack.append(i)

3. 알파벳이 아니고 i가 *거나 /일 때, 스택에 쌓는다.
   ✅
   그 전에 answer에 어떤 조건으로 스택의 마지막을 answer에 쌓는지 생각해야한다.
   만약 A*B*C일 때, AB*C*로 변경되어야 하기 때문에
   스택에 값이 있고 스택의 마지막 값이 거나 /일 때 스택에 있는 첫번 째 을 answer에 쌓는 식을 작성한다.

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

4. 알파벳이 아니고 i가 +거나 -일 때, 스택에 쌓는다.
   ✅
   그 전에 answer에 어떤 조건으로 스택의 마지막을 answer에 쌓는지 생각해야한다.
   만약 (A+B)일 때, 스택의 마지막 값이 ( 면 스택에는 +가 들어있지 않은 상태이기 때문에, answer에는 값이 [a, ( ] 이렇게 쌓인다. 그렇기 때문에 +까지 스택에 쌓아야 문자열에 값이 [a, b, +]로 들어오게 된다.

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

5. 괄호를 모두 지워주는 작업을 한다.
   ✅
   만약 (A+B)일 때, 스택: [ ( , +] / answer: "A", "B" 이 쌓여있다.
   이때, ) 가 들어오고 스택의 마지막 값이 +이기 때문에 스택의 마지막 값인 +가 answer에 더해진다.
   -> 스택: [ ( ] / answer: "A", "B", "+"
   
   while문이라 또 한 번 돌게 되는데, 스택의 마지막 값이 ( 이기 때문에 while문은 종료된다.
   -> 스택: [ ( ] / answer: "A", "B", "+"
   
   그 후 스택 마지막 값인 ( 를 지운다.
   -> 스택: [ ] / answer: "A", "B", "+"

elif i == ')':
    while stack and stack[-1] != '(':
          answer += stack.pop()
    stack.pop()

6. 스택에 남는 값은 다 answer에 더해준다.

while stack:
    answer += stack.pop()