[백준 알고리즘/Python3] 1918 후위 표기식

문제이해

후위 표기식은 중위 표기식에서 문자,숫자를 제외한 문자를 후위에 두는 것 입니다. 이 때 각 연산자는 우선순위가 있습니다.

• *,/ 는 1순위
• +,-는 2순위 
• (,)는 3순위

문자는 그대로 출력하고 스택에 연산자만 들어가게끔 합니다. 스택 연산자가 들어갈 때 스택 최상위 것의 우선순위가 현제 들어갈 문자보다 크다면 pop()을 합니다. 

ex) 스택에 [+,*] 이 들어가 있을 때 '-'가 들어갈 차례가 됐습니다. '*'의 우선순위는 1순위 이고, '-'의 우선순위는 2순위 이니 *를 pop()합니다. 다음 '+'와 '-' 우선순위를 비교하는데 순위가 같으니 push만 합니다.

 

'('이 들어가면 연산의 우선순위가 높은 것이니 ')'이 나올 때까지 연산자를 pop()합니다.

코드

#연산자의 우선순위
def prec(n):
    if(n == '(' or n == ')'):
        return 0
    elif(n == '+' or n == '-'):
        return 1
    elif(n == '*' or n == '/'):
        return 2

#식 입력
calculation = input()


stack =[]

for i in calculation:
    #문자가 숫자이면
    if(i.isalnum()):
        print(i, end='')
    else:
        if (i == '+' or i == '-' or i == '*' or i == '/'):
            #우선순위가 늪은 것이 스택 밑에 있다면 낮은거 있을 때까지 pop()
            while(stack != [] and prec(i) <= prec(stack[-1])):
                print(stack.pop(), end='')
            stack.append(i)

        elif(i == '('):
            stack.append(i)
            
        elif(i == ')'):
            k = stack.pop()
            while(k != '('):
                print(k, end='')
                k = stack.pop()
    
while(stack != []):
    print(stack.pop(), end='')

마지막 남은 연산자가 있다면 모두 출력해줍니다. 마지막에 pop()됐다는건 제일 마지막에 연산되었다는 뜻입니다.