[CodingTest] BOJ1918 후위표기식 ( 자료구조 ) With 파이썬

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

1918번: 후위 표기식

 

◎문제풀이

 

우선순위와 STACK의 연관성을 이해하면 쉽게 풀리는 문제이다. 

 

A,B,C,D는 우선순위가 없이 순서대로 출력하면 된다.

반면 연산자는 우선순위가 있다. 우선순위대로 출력되어야 한다. 

 

*,/ 는 우선순위가 높다.

+,-는 우선순위가 낮다.

 

우선순위가 높은 연산자가 먼저 출력되어야 한다. 

 

STACK은 LIFO이다. 그러므로 우선순위가 높은 연산자가 위에 있어야 한다. 그래야 먼저 POP된다. 우선순위가 낮은 연산자를 PUSH하려면 우선순위가 높은 연산자를 모두 POP하고 난 뒤, STACK에 PUSH할 수 있다. 그리고 여기에는 한 가지 변수가 있다. 바로 괄호이다. 괄호 안에 있는 연산자는 우선순위가 높다. 그러므로 자신보다 우선순위가 높은 연산자를 계속 POP하다가 '('를 만나면 POP을 중단하고 PUSH한다. STACK에서 '(' 아래에 깔린 연산자들은 곱하기든 나누기든 본인보다 우선순위가 낮기 때문이다. 

 

')'를 만나면, ( ) 괄호가 성립함을 의미한다. 괄호 안에 있는 연산자는 이후 등장할 연산자보다 무조건 우선순위가 높다. 그러므로 STACK에서 '('를 만날때까지 연산자들을 POP한다. 

 

TIP) 우선순위는 딕셔너리 자료형으로 쉽게 구현할 수 있다.

 

◎코드

import sys
input = sys.stdin.readline

infix = list(input().rstrip()) 
postfix = [] # 후위표기식 
stack = [] # 연산자 스택
priority = {'+': 1 , '-' : 1, '*' : 2, '/' : 2,'(': 0} # 우선순위 딕셔너리


for x in infix :
  if x.isalpha() : postfix.append(x) # 문자인 경우 바로 출력
  elif x == "(" : stack.append(x) # ( 이면 바로 STACK에 PUSH
  elif x == ")" : 
    while stack[-1] != "(" : # ) 나오면 이후, 연산자는 우선순위가 무조건 낮으므로 ( 를 만날때까지 POP
      postfix.append(stack.pop())
    stack.pop()
  else : # 괄호가 아닌 연산자인 경우
    while stack and priority[x] <= priority[stack[-1]] : # 우선순위가 STACK의 TOP 연산자보다 낮은 경우
      postfix.append(stack.pop()) # 높은 우선순위를 가진 연산자 모두 POP
    stack.append(x) # 우선순위 높은 연산자가 이제 없으므로 PUSH

#남은 연산자 마지막으로 POP ( 털기 )
while stack : postfix.append(stack.pop())

#출력
for value in postfix :
  print(value,end="")