[Python] 백준 - 1918번 후위 표기식(Stack)

◈ 오류 정정 및 피드백 환영

1918번: 후위 표기식

---

🔎문제 분석

연산자가 나오기 전까지는 입력 받은 피연산자를 어떻게 연산해야 할지 알 수 없다. 따라서 연산자를 어떤 곳에 넣어두었다가 특정 조건을 만족하면 다시 꺼내 연산해야 하며, 이를 위해 스택(Stack)으로 접근하면 된다.

 

피연산자가 나오면 바로 출력한다.

if i.isalpha():
    res += i

연산자가 나오면 바로 판단하지 말고 우선 스택에 저장한다.

그리고 다음 연산자가 나왔을 때 다시 꺼내 연산이 가능한지를 살펴본 뒤 출력한다.

 

쉽게 생각하기 위해 괄호는 없다고 전제하고 다음을 비교해 보자. 

Ex 1
A+B*C-D/E → ABC*+DE/-

Ex 2
A*B*C-D/E → AB*C*DE/-

2번째 연산자인 *가 나왔을 때 스택에 들어있던 연산자를 출력하는지 여부는 해당 연산자가 +인지 *인지에 달려있다.

+인 경우에는 출력하지 않았고 *인 경우는 출력했다. 이는 연산자의 우선순위가 *가 더 높기 때문이다. 즉, 스택에 여러 개의 연산자가 들어있을 때 어떤 연산자까지 꺼내야 할지를 결정하기 위해서는 우선순위를 고려해야 한다.

 

만약 * 또는 / 가 나와 스택에 저장된 연산자를 살펴보는데 + 또는 -만 들어있다면 꺼내서는 안 된다(Ex 1). * 또는 /의 우선순위가 더 높기 때문에 먼저 연산이 되어서는 안 되기 때문이다. 즉, 이 경우에는 * 또는 /만 꺼내야 한다.

if i in ["*","/"]:
    while stack and stack[-1] in ["*","/"]:
        res += stack.pop()
stack.append(i)

반대로 + 또는 -가 나왔다면 별 조건 없이 바로 스택에 있는 연산자를 꺼내도 된다. * 또는 /라면 우선순위가 더 높기에 상관없고, + 또는 -일지라도 앞서 나온 연산자부터 처리하는 것이 맞기 때문에 상관없기 때문이다.

 

이번에는 괄호를 넣어서 비교해 보자. 

Ex 1
A*B+C*A*B+C+A*B+C → AB*CA*B*+C+AB*+C+

Ex 2
A*B+C*(A*B+C)+A*B+C → AB*CAB*C+*+AB*+C+

C와 A를 출력하고 *가 나왔을 때 스택에 들어있던 3번째 연산자인 *를 출력한 Ex 1과 달리 Ex 2에서는 출력하지 않았다. 그 이유는 바로 스택에 들어있던 (이다. 이로 인해 위에서 설정한 조건(* 또는 /만 꺼내야 한다)에 어긋나므로 스택에 있는 연산자 (를 꺼내고 *를 마저 꺼낼 수가 없다. *는 괄호 안의 연산보다 우선순위가 낮기 때문이다. 

 

따라서 괄호 안의 연산임을 확인해야 한다. 즉, + 또는 -가 나왔을 때 이제 조건을 추가해야 한다.

if i in ["+","-"]:
    while stack and stack[-1] != "(":
        res += stack.pop()

그렇지 않으면 괄호 안의 연산이 끝나지 않았음에도 괄호 바깥의 연산자 *까지 출력할 위험이 있기 때문이다.

 

)는 괄호 안의 연산이 끝남을 알려주기 때문에 괄호 안에 남아있던 연산자를 모두 출력하면 된다.

if i==")":
    while stack and stack[-1] != "(":
        res += stack.pop()
    stack.pop()

괄호 안의 연산이 끝났다면 남아있던 스택에 있는 연산자 *를 꺼내 미뤄두었던 연산을 하면 된다.

 

🤦‍♀️유의 사항

)는 괄호 위치를 판단하기 위한 연산자일 뿐 굳이 스택에 저장할 필요가 없다.

---

import sys
input = sys.stdin.readline

a = list(input())
stack = []
res = ''
for i in a: 
    if i.isalpha():
        res += i
            
    elif i in ["+","-","*","/","("]:
        if i in ["+","-"]:
            while stack and stack[-1] != "(":
                res += stack.pop()
        elif i in ["*","/"]:
            while stack and stack[-1] in ["*","/"]:
                res += stack.pop()
        stack.append(i) 
        
    elif i==")":
        while stack and stack[-1] != "(":
            res += stack.pop()
        stack.pop()
        
res += ''.join(stack[::-1])          
print(res)