스택&큐(유형정리) - 백준 1935

1935번: 후위 표기식2 (acmicpc.net)

1935번: 후위 표기식2

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

예제 입력 1 복사

5
ABC*+DE/-
1
2
3
4
5

예제 출력 1 복사

6.20

예제 입력 2 복사

1
AA+A+
1

예제 출력 2 복사

3.00

 

흔히 스택&큐를 배울 때 후위표기식을 한번은 다루게 된다.

후위표기식에 대한 스택 쌓기는 다른 블로그들을 참고하면 될 것 같아 굳이 따로 설명하지는 않겠다.

 

이 프로그램에서 예를 간단히 들어서 어떻게 예제 계산이 저런 결과를 내놓았는지를 살펴보자.

 

먼저 첫번째 예시에서 ABC*+DE/- 라는 후위표기식이 있다. 여기서 각 알파벳을 입력 받아 A=1, B=2, C=3, D=4, E=5의 값으로 연산을 풀게 된다. 그렇다면 123*+45/- 와 같은 식이 된다.

 

1. 2*3 = 6

2. 1+6 = 7

3. 4/5 = 0.xx

4. 7-0.xx = 6.xx

 

이렇게 계산이 적용되어 6.20의 값을 도출해 낼 수 있게 된다.

 

※ 알고리즘

1. 몇개의 알파벳을 입력받을 것인지 정하는 변수 N

2. 후위표기식 문자열

3. N크기의 알파벳을 입력받을 리스트 선언

4. 알파벳 리스트에 N개만큼 반복적으로 숫자를 입력받음.

5. 결과를 뽑아낼 빈 리스트 result

6. 후위표기식 내부를 반복문으로 설정하고, 알파벳일 경우 result 리스트에 알파벳 리스트에서 숫자를 뽑아내어 담는다.

-> alphabet[ord(i) - 65] : 65는 'A'의 아스키코드 값

7. 후위표기식 자체가 숫자면 push하고, 연산자면 pop하는 것이기 때문에 +,-,*,/ 일때 숫자를 pop해서 연산을 시켜준다.

8. 결과를 모두 result 리스트에 담아서 출력시킨다.

 

N = int(input())
func = input()
alphabet = [0]*N

for i in range(N):
    alphabet[i] = int(input())

result = []

for i in func:
    if i.isalpha():
        result.append(alphabet[ord(i) - 65])
    else:
        str2 = result.pop()
        str1 = result.pop()

        if i == '+':
            result.append(str1 + str2)
        elif i == '-':
            result.append(str1 - str2)
        elif i == '*':
            result.append(str1 * str2)
        elif i == '/':
            result.append(str1 / str2)

print("%.2f" %result[0])