백준 1918번: 후위 표기식

문제링크: 1918번: 후위 표기식 (acmicpc.net)

1918번: 후위 표기식

중위 표기로 주어진 식을 후위 표기하여 반환하는 문제이다. 딱히 방법이 생각도 안나고 후위 표기라는 것도 처음 들어봐서 어려운 문제였다. 특히 괄호가 있는점이 복잡해 보였고 문제에서 설명하는 과정 처럼 a+b*c -> (a+(b*c)) 이렇게 사칙연산의 우선순위에 따라 괄호를 쳐주고, 괄호 순서대로 후위 표기를 하는 알고리즘을 만든다면, 두개의 알고리즘을 만들어야 하고, 사칙연산의 부호에 대해 괄호를 쳐주는 알고리즘을 만드는 것이 더 복잡할 것 같았다.

 

내가 선택한 방법은 일단 괄호가 전혀 없다고 가정하고 후위 표기식을 하는 함수를 만드는 것이었다. 괄호가 전혀 없다는 가정 하에는 사칙연산의 우선순위만 고려해주면 되기 때문에 후위 표기식을 만드는 것이 쉬울 것 같았다. 밑에 코드를 보면 nopar(w)라는 함수를 만들어서 식이 리스트 형태로 입력(w) 이 주어지면 (예시 ['A','+','B','*','C']) 그것을 후위 표기해서 문자로 반환하는 함수를 만들었다. 먼저 곱셈, 나눗셈 이 먼저이므로 단일의 *,/ 부호가 없어질 때까지 후위 표기해 주는 방식을 사용하고 다음으로 +,-부호가 없어질 때까지 후위 표기를 했다.

 

실제 문제는 괄호를 고려해야 한다. 보통 괄호가 있는 식이 주어지면 사람은 가장 깊은 괄호 안쪽을 먼저 계산하여 괄호를 풀어주고, 다음 괄호를 계산하는 방식으로 식을 풀어 나간다. 최대한 같은 원리를 사용하여 가장 깊은 괄호부터 계산하는 방식을 사용하였다.

 

괄호를 해결하기 위해 괄호의 깊이를 뜻하는 parcount라는 괄호가 열릴때마다 +1되고 닫히면 -1되는 상수를 선언하고괄호에 깊이에 따라 식의 문자들을 callist에 저장했다. callist의 인덱스는 괄호의 깊이를 뜻한다. 식의 길이가 100이라고 했으므로 전부 괄호라고 해도 괄호의 깊이가 50이기 때문에 인덱스 50까지 2차원 리스트를 만들어 주었다. 괄호가 열리고 괄호의 깊이가 늘어나다 만약 괄호가 닫히면 그 닫힌 괄호의 식(괄호의 깊이가 가장 깊은)을 계산해야 하기에 back=1을 선언하여 계산해야 함을 알려주었고 닫힌 괄호의 식을 아까 만든 함수 nopar(w)를 이용하여 후위 표기하여 더 낮은 괄호 깊이에 저장해주었다. 이렇게 괄호를 깊은곳부터 모두 풀어 나가면 마지막에 괄호의 깊이가 0 인 식이 저장되고 마지막으로 nopar를 이용해 후위 표기해주면 답이 나오게 된다.

 

만약 A+(B-(C+D)-(E+F)) 라면 callist[2]에 C,+,D 가 저장되고 괄호가 닫히는 순간 CD+로 반환되어 calist[1]에 저장된다. 여기서 후위 표기가 완료되면 calist[2]=[]로 리스트를 비워 줘서 다음 (E+F)를 계산할 수 있도록 한다.

from collections import deque
import sys

def nopar(w): #w=list() 만약 괄호가 하나도 없을때 식을 후위 표기하여 반환
    global sign
    while '*' in w or '/' in w: #곱셉, 나눗셈 기호가 전부 없어질때까지 후위 표기
        for i in range(len(w)):
            if len(w)>i:
                if (w[i]=='*' or w[i]=='/') and w[i+1] not in sign:
                    w[i-1]=(w[i-1]+w[i+1]+w[i])
                    del w[i]
                    del w[i]  
                    break
    while '+' in w or '-' in w: #덧셈, 뺼셈 기호가 전부 없어질때까지 후위 표기
        for i in range(len(w)):
            if len(w)>i:
                if (w[i]=='+' or w[i]=='-') and w[i+1] not in sign:
                    w[i-1]=(w[i-1]+w[i+1]+w[i])
                    del w[i]
                    del w[i]
                    break

    return w[0]


s=sys.stdin.readline().rstrip()

letter=list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
sign=list('+-*/()')
wordlst=deque(list(s))
callist=[[] for _ in range(51)] #최대 길이가 100이므로 괄호의 깊이는 최대 50
parcount=0

while wordlst:
    back=0
    x=wordlst.popleft()
    if x=='(': #괄호가 열릴때마다 parcount+=1 괄호의 깊이가 올라간다
        parcount+=1
    elif x==')': #괄호가 닫히면 parcount-=1 괄호의 깊이가 낮아지고 닫힌 괄호의 식을 후위 표기해주기 위해 back선언
        parcount-=1
        back=1
    elif x in letter:
        callist[parcount].append(x)
    elif x=='+' or x=='-':
        callist[parcount].append(x)
    elif x=='*' or x=='/':
        callist[parcount].append(x)
    if back==1: #괄호가 닫혔으므로 최대 깊이의 식을 후위 표기하여 최대깊이-1 깊이에 넣어준다.
        callist[parcount].append(nopar(callist[parcount+1]))
        callist[parcount+1]=[] #계산한 기존 식은 삭제
        
# 위 과정을 마치면 callist[0], 즉 괄호 깊이가 0인 곳에 전부 정리된다. 마지막으로 nopar를 해준다.
print(nopar(callist[0]))