[BOJ, Python] 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

 

풀이

stack을 활용하는 문제입니다. 후위 표기식의 성질을 잘 파악하면 쉽게 풀수있는 문제입니다.

 

제가 생각하는 이 문제의 핵심은 pop - pop - push입니다!

 

이게 무슨말이나면, ABC*+DE/- 이런 식으로 후위 표기식이 입력으로 주어질 때, 첫 번째 operand(A)부터 push를 하다가 operator를 만나면 pop - pop - push를 하는 것입니다.

 

후위 표기식을 만족하도록 입력이 주어지기 때문에, pop을 두 번하더라도 index error가 나타나지 않음이 보장됩니다.

각 pop에 대한 return 값을 op1, op2에 저장하고, 입력된 operator에 따라서 op2 +. -. *, / op1 연산을 수행한 뒤, 그 값을 다시 stack에 push 합니다.

 

모든 operator에 대해 이 과정을 반복하면 최종 연산 결과만 stack에 남게 됩니다.

 

코드는 다음과 같습니다.

N = int(input())
equation = input()

operands = []
stack = []

for _ in range(N):
    operands.append(int(input()))

for x in equation:
    if x == "+":
        op1 = stack.pop()
        op2 = stack.pop()
        result = op2 + op1
        stack.append(result)
        
    elif x == "-":
        op1 = stack.pop()
        op2 = stack.pop()
        result = op2 - op1
        stack.append(result)
     
    elif x == "*":
        op1 = stack.pop()
        op2 = stack.pop()
        result = op2 * op1
        stack.append(result)
       
    elif x == "/":
        op1 = stack.pop()
        op2 = stack.pop()
        result = op2 / op1
        stack.append(result)
        
    # else에서 operand push, ascii code를 활용해 알파벳과 index matching
    else:
        index = ord(x) - ord("A")
        stack.append(operands[index])

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