[백준 파이썬] 1918 후위 표기식

 

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

문제

 

중위표기식으로 표현된 식을 후위 표기식으로 바꾸는 문제이다.

---

 

풀이

우리가 흔히쓰는 식은 모두 중위표현식이다. 이를 후위표기식으로 바꾸는 예시는 다음과 같다.

A*(B+C) -> ABC+*

A+B -> AB+

 

이런식으로 후위표기식으로 바꾸기 위해서는 다음의 조건을 만족해야한다.

1. 피연산자는 그대로 출력한다.

2. 연산자는 스택에 추가한다.

2.1 이 때 스택의 가장 위에있는 연산자가 자신보다 낮은순위의 연산자가 될 때 까지 현재 스택에서 pop하여 출력한 뒤 자신을 스택에 추가한다.

3. 여는 괄호가 만날 시 스택에 추가한다.

4. 닫는 괄호가 만날 시 여는 괄호가 나올때 까지 스택에서 pop하여 출력한다. 이 때 여는괄호는 출력하지 않는다.

 

해당 조건들을 적용하여 코드를 작성한다.

 

for i in infix:
    if i == "(":
        q.append(i)
    elif i == ")":
        while True:
            tmp = q.pop()
            if tmp == "(":
                break
            print(tmp, end="")
    elif i == "*" or i == "/":
        while q and (q[-1] == '*' or q[-1] == '/'):
            print(q.pop(), end="")
        q.append(i)
    
    elif i == '+' or i == '-':
        while q and q[-1] != '(':
            print(q.pop(), end="")
        q.append(i)
            
    else:
        print(i, end="")

 

 

이 후 스택에 있는 모든 연산자들을 순서대로 pop하여 출력한다.

while q:
    print(q.pop(), end="")

 

 

코드

from collections import deque
# 1. 피연산자는 그대로 출력
# 2. 연산자는 스택에 추가
# 2-1 이 때 스택의 top이 자신보다 우선순위가 낮은 연산자를 만날때까지 pop 한 뒤 자신을 담음
# 3. 여는 괄호가 나올 시 스택 추가
# 4. 닫는 괄호가 나올 시 여는 괄호가 나올때까지 스택에서 pop


infix = list(input())

q = deque()

for i in infix:
    if i == "(":
        q.append(i)
    elif i == ")":
        while True:
            tmp = q.pop()
            if tmp == "(":
                break
            print(tmp, end="")
    elif i == "*" or i == "/":
        while q and (q[-1] == '*' or q[-1] == '/'):
            print(q.pop(), end="")
        q.append(i)
    
    elif i == '+' or i == '-':
        while q and q[-1] != '(':
            print(q.pop(), end="")
        q.append(i)
            
    else:
        print(i, end="")

while q:
    print(q.pop(), end="")