[백준/python] 1935 후위 표기식2

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

1935번: 후위 표기식2

 

• 사용언어 : python
• 알고리즘 : 자료구조, 스택
• Solved.ac Tier : Silver IV

 

 

python 코드

1. 문제 정리

후위 표기식, 전위 표기식은 전공자가 아니라면 듣기 어려운 식들이다. 후위 표기식은 컴퓨터가 사용하는 연산 방법으로, 왼쪽에서 오른쪽으로 표기된 순서대로 처리하면 결과가 올바르게 나오는 후위 표기법을 사용한다. 

스택을 사용하여 원래의 중위 표기식으로 변환할 수 있다. 이번 문제는 그렇게 해결하였다. 위 그림을 보면 피연산자(알파벳)가 나오면 스택에 담아주고, 연산자가 나온다면 피연산자 2개를 꺼내서 계산 한 뒤 다시 stack에 넣어주는 방식으로 문제를 해결하였다. 

코드를 살펴보자. 

for str in line:
    if(str.isalpha()):
        deq.append(list[ord(str) - 65]) #ord는 알파벳을 아스키코드로 변환해준다. 알파벳 A의 아스키코드는 65이다
    else:
        first = deq.pop()
        second = deq.pop()
        deq.append(eval(f"{second} {str} {first}"))

2번째줄을 line으로 두었다. line의 각각 글자들을 확인하여 isalpha() 함수를 사용하여 알파벳(피연산자)이면 3,4,5.... 번 줄에 있던 숫자들을 list에 넣어두었는데, 그 리스트에 해당하는 값을 넣어주었다. 

for i in range(N):
    list.append(int(input()))

3번째 줄부터 N개의 입력을 받아와 A부터 N개만큼 알파벳에 해당하는 값을 가져와 주었다. ord(str)-65는 str이 A일 경우 0이된다. 따라서 위의 deq.append(list[ord(str) - 65])값은 str이 A일 경우 3번째 줄에 입력받은 A 값을 deq에 push 해주는 것과 같은 역할을 한다.

만약 str의 값이 연산자라면, 값들을 pop 해와서 eval 함수를 통해 문자여도 연산이 가능하도록 만들었다. 

 

2. 완성 코드

import sys
from collections import deque
deq = deque()
list = list()
N = int(input())
line = sys.stdin.readline().rstrip()
ans = 0

for i in range(N):
    list.append(int(input()))

for str in line:
    if(str.isalpha()):
        deq.append(list[ord(str) - 65])
    else:
        first = deq.pop()
        second = deq.pop()
        deq.append(eval(f"{second} {str} {first}"))

print("{:.2f}".format(deq[0]))