문제

[백준] 후위 표기식 (Gold 2)

요약

후위 표기법이란, 연산자가 피연산자 뒤에 위치하는 수식 표기법을 말한다.

분류

  • 스택

풀이

1. 내 풀이 (스택)

중위 표기식을 후위 표기식으로 전환하는 방법은 의외로 간단하다. 가장 먼저 계산되는 연산자부터 피연산자들 뒤로 위치를 바꿔주면 된다. 이렇게 완성된 (피연산자 피연산자 연산자) 조합은 또 하나의 피연산자가 된다. 이때 연산자의 우선순위를 판별하는 데 스택을 사용한다.

후위 표기식의 중요한 특징은, 중위 표기식과 비교할 때 피연산자들의 상대적인 순서가 변하지 않는다는 것과, 연산자는 먼저 계산되는 순서대로 정렬된다는 것이다.

다음과 같은 과정을 통해 후위 표기식을 얻을 수 있다.

  1. 피연산자는 그대로 출력한다.
  2. 연산자가 만약
    1. ( 라면, 스택에 push 한다.
    2. ) 라면, ( 가 나올 때까지 스택에서 pop한 결과를 출력한다.
    3. +, -, *, / 의 연산자라면, 스택의 top에 현재 연산자보다 더 우선순위가 낮은 연산자가 나올 때까지 스택에서 pop한 결과를 출력한다.
  3. 더 이상 순회할 수식의 요소가 남아있지 않다면 스택에 남아 있는 연산자들을 역순으로 출력한다.

이러한 과정을 코드로 나타내면 다음과 같다.


def precedence(op):
  if op == "(" or op == ")":
    return 0
  elif op == "+" or op == "-":
    return 1
  elif op == "*" or op == "/":
    return 2

o = input()
stack = []
ans = []
for s in o:
  if s == "(":
    stack.append("(")
  elif s == ")":
    while stack:
      op = stack.pop()
      if op == "(":
        break
      else:
        ans.append(op)
  elif s in "+*/-":
    while stack:
      op = stack[-1]
      if precedence(op) >= precedence(s):
        ans.append(stack.pop())
      else:
        break
    stack.append(s)

  else:
    ans.append(s)

while stack:
  ans.append(stack.pop())

print(''.join(ans))