[Python 3] BOJ - 1918 "후위 표기식"

 # 문제 링크 : https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

 # 풀이 :

 후위 표기식에 대한 자세한 설명은 문제에 설명 되어 있으므로 생략한다. 개인적으로 문제의 핵심은 스택을 자료구조로 이용해야 한다는 점, 스택을 2개를 써야 한다는 점이다. 연산자의 우선순위와 괄호의 우선순위를 성립하게 하기 위해 연산자와 괄호의 우선순위를 임의적으로 저장해야 한다. 스택을 두개로 나누는 이유는 알파벳은 우선순위가 없으므로 바로 후위 표기식 스택에 저장하고, 연산자가 오는 경우는 다음의 그림과 같은 과정으로 이루어진다. 

<그림 1. a + b * c의 경우 (1)>

 초기에 연산자 스택, 후위 표기 스택 모두 비어있고 항상 모든 식은 맨 처음엔 알파벳부터 시작하므로 첫번째 알파벳인 'A'가 후위 표기 스택에 들어간다. 또한 연산자 스택이 비어있으므로 어느 경우든 가능하므로 '+'도 연산자 스택에 넣는다. 'B'는 알파벳이므로 우선순위가 없다. 따라서 후위 표기 스택에 바로 넣어 준다. 문제는 '*', 곱하기 연산자를 넣어야 하는 경우이다. 만일 우선순위를 고려하지 않고 그대로 연산자 스택에 추가한다면, 후위 표기식을 계산할 때 곱하기 보다 더하기를 먼저하는 경우가 생기므로 현재 스택의 '+'를 pop하여 후위 표기 스택에 넣고 연산자 스택이 비었기 때문에 '*'를 연산자 스택에 넣어준다.

<그림 2. a + b * c의 경우 (2)>

  이후, 'C'도 알파벳이므로 그대로 후위 표기식 스택에 넣어준다. 식이 끝났으므로 연산자 스택에 남은 연산자들을 순서대로 pop하여 후위 표기 스택에 넣어주면 정답을 구할 수 있다. 만일 괄호가 있는 경우는 어떨까? 

<그림 3. (a + b * c)의 경우 (1)>

 '(', 즉 여는 괄호는 ')', 닫는 괄호를 만나기 전까지는 연산자 스택에 있어야 한다. 만일 닫는 괄호를 만나지 않은 상태인데 그림 1과 같이 연산자들 끼리의 우선순위가 충돌하면 그림 1에서의 논리를 유지하면 된다. 그러나 현재가 닫는 괄호라면 여는 괄호가 나올때까지 연산자 스택의 모든 연산자들을 pop해야 한다. 그렇지 않다면 연산자 간의 우선순위는 지켜질 지 몰라도, 괄호의 우선순위를 고려하지 못하기 때문이다. 한가지 유의할 점은 닫는 괄호는 여는 괄호가 나올 때 까지 pop를 하고 연산자 스택에 담지 않는다는 것이다. 왜냐하면 여는 괄호는 닫는 괄호를 통해 완성되지만 역은 성립하지 않기 때문에, 즉 닫는 괄호 스스로도, 순서가 바뀐 경우에도 - 보통 ( ~~~ ) 의 경우가 아니라 ) ~~~ ( 의 경우는 무의미한 것 처럼 - 무의미하기 때문이다. 또한 문제의 후위 표기식에는 괄호가 없으므로 여는 괄호도 후위 표기 스택에 넣지 않는다. 그 이후 처리는 괄호가 다시 나타난다면 그림3, 그렇지 않다면 그림1과 같으며 종국에는 그림2의 경우가 된다.

<그림 4. (a + b * c)의 경우 (2) >

 # 코드

import sys

n = list(sys.stdin.readline().rstrip())

# 연산자의 우선순위를 dict형태로 저장
oper_dict = {'+' : 1, '-' : 1, '*' : 2, '/' : 2, '(' : 0}

postfix = []
stack = []
ans= ''
for i in n:
    # 알파벳이면 후위 표기 스택에 바로 넣는다
    if 'A' <= i <= 'Z':
        postfix.append(i)
    # 여는 괄호면 연산자 스택에 바로 넣는다
    elif i == '(':
        stack.append(i)
    elif i == ')':
        # 연산자 스택이 비거나 여는괄호를 만날 때 까지 pop
        while stack and stack[-1] != '(':
            postfix.append(stack.pop())
        # 이 때의 pop은 여는 괄호이므로 후위 표기 스택에 저장하지 않는다
        stack.pop()
    else:
        # 현재 연산자가 스택의 top 연산자보다 우선순위가 높은 경우
        while stack and oper_dict[i] <= oper_dict[stack[-1]]:
            postfix.append(stack.pop())
        # 그렇지 않은 경우거나 낮은 우선순위를 가진 연산자를 모두 pop한 경우
        stack.append(i)
        
# 항상 연산자 스택에는 하나 이상의 연산자가 존재하므로 스택을 비워준다
while len(stack) != 0:
    postfix.append(stack.pop())
    
# 정답 출력
for i in postfix:
    ans += i
print(ans)