[백준 1918번] 파이썬 - 후위 표기식

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

 

 

# 조건

• 수식은 일반적으로 중위 표기법, 전위 표기법, 후위 표기법으로 나타낼 수 있다.
• 이 문제에서는 후위 표기법으로 나타내는데 연산자가 피연산자 뒤에 위치하는 방법
• 예를 들어 a+b c를 후위 표기식으로 바꾸면 abc +가 된다.
• 바꾸는 방법
  • 주어진 중위 표기식을 연산자의 우선 순위에 따라 괄호로 묶어준다.
  • 그런 다음 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.
    
     

# 접근 방법

• 문제에 나와있는 방식을 스택을 이용해서 구현해주면 된다.

1. 입력받은 표기식에서 토큰을 읽는다.
2. 토큰이 피연산자이면 토큰 출력
3. 토큰이 괄호를 포함한 연산자일 때, 토큰이 스택의 TOP에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 PUSH 하고, 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop 한 후 토큰 연산자를 push 한다. 만약 top에 연산자 없으면 push
4. 토큰이 ')'이면 스택 top에 '('가 올 때까지 스택에 pop연산 수행하고 pop한 연산자 출력
5. 더 읽을 것이 없다면 중지, 읽을 것이 있다면 1부터 다시 반복
6.  
   스택에 남아있는 연산자를 모두 pop하여 출력
   • 스택 밖의 왼 괄화는 우선순위가 가장 높지만, 스택 안의 왼쪽 괄호는 우선순위가 가장 낮다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

words = input().strip()
idx = 0
result = ''
temp = []
prior = {'*':3,'/':3,'+':2,'-':2,'(':1, ')':0}
while idx < len(words):
    v = words[idx]
    if v.isalpha():
        result += v
    elif v == '(':
        temp.append(v)
    elif v == ')':
        while temp[-1] != '(':
            result += temp.pop()
        temp.pop()
    else:
        while temp and prior[v] <= prior[temp[-1]]:
            result += temp.pop()
        temp.append(v)
    idx += 1
while temp:
    result += temp.pop()
print(''.join(result))