[백준 BOJ_1918] 후위 표기식 Python 풀이

출처: 백준 온라인 저지

문제

풀이

Stack을 이용하여 풀어주었습니다.

각각 연산의 우선순위를 저장해주는 priority라는 dictionary를 만들어주었습니다. 먼저 계산이 되어야 할 곱셈, 나눗셈은 2로, 덧셈과 뺄셈은 1로, 그리고 연산은 아니지만 stack에 들어가게 되어 빼주어야 하기 때문에 괄호는 0으로 지정해주었습니다.

중위표기식인 infix의 글자를 하나씩 체크하며 알파벳 대문자일 경우에는 바로 postfix에 추가해주었습니다. 그렇지 않을 경우에는 열린 괄호(“(“)라면 stack에 추가를 해주고 닫힌 괄호(“)”)라면 그동안 stack을 열린 괄호를 찾을 때 까지 pop해주며 postfix에 pop해준 글자를 추가해주었습니다.

괄호가 아닌 연산이라면, stack에서 해당 연산보다 우선순위가 높거나 같은 연산들까지만 pop해주어 postfix에 넣어줍니다.

모든 글자를 다 체크해준 뒤에도 stack에 글자가 남았다면 남기지 않고 pop해주어 postfix에 추가해준 뒤, postfix를 출력해줍니다.

코드

infix = input()
priority = {"*": 2, "/": 2, "+": 1, "-": 1, "(": 0}
postfix = []
stack = []
for ch in infix:
  if ord("A") <= ord(ch) <= ord("Z"):
    postfix.append(ch)
  else:
    if ch == "(": 
      stack.append(ch)
    elif ch == ")":
      while 1:
        popped = stack.pop()
        if popped == "(": 
          break
        postfix.append(popped)
    else:
      while stack and priority[ch] <= priority[stack[-1]]:
        postfix.append(stack.pop())
      stack.append(ch)
while stack:
  postfix.append(stack.pop())
print("".join(postfix))