백준 1935번: 후위 표기식2(S3)

 

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

1935번: 후위 표기식2

 

✨ 문제

 

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

 

 

✨ 접근방법

 

- stack을 이용하여 피연산자는 stack에 저장해주고, 연산자를 만났을 경우에는 stack에서 값을 pop해서 계산해준 뒤 다시 stack에 pop하는 방식으로 구현하였다.

 

- 다만 문제의 조건이 뚜렷하지 않아 예외처리를 하기 애매하다고 느껴졌다. 

 

 

 

✨ 후위 표기법

 

- 이 문제는 후위 표기법을 알아야 풀 수 있는 문제이다. 몇년 전 자료구조 시간에 후위 표기법을 배웠지만 막상 다시 보니 잘 기억이 나지 않았기에 복습을 해보자 👊

 

- 일반적으로 우리가 보는 수학적 표현이나 계산을 위한 표기법을 중위 표기법이라고 한다. 예를들어 (3+4) X 5와 같은 표현이 중위 표현법이다.

 

- 후위 표기법은 중위 표기법처럼 수학 계산을 위한 표기법 중 하나로 괄호의 사용을 최소화하고 계산 우선순위를 명확하게 표현할 수 있다는 장점이 있다.

 

- (3+4) X 5를 후위 표기법으로 바꾸면 34+5X처럼 나타낼 수 있다.

 

- 이때 계산 순서는 연산자가 나오는 대로 왼쪽에서 오른쪽 순서대로 계산을 하게 된다. 위의 예시에서는 먼저 3과 4를 더한 후에 그 결과를 5에 곱하게 된다. 

 

- 이를 stack이라는 자료구조에 접목하여 설명하면 후위 표기법에서 숫자를 만나면 stack에 append 해주고 연산자를 만나면 stack에서 숫자 두 개를 pop한뒤 stack에 먼저 들어갔던 요소를 왼쪽 기준, stack에 늦게 들어갔던 요소를 오른쪽을 기준으로 계산하고 다시 stack에 숫자를 append해주면 된다.

 

- 3과 4를 생각해보면 스택에는 3이 먼저 들어가고 4가 나중에 들어갈 것이다. 이때 계산은 3+4의 순서로 이루어진다. 덧셈이나 뺄셈, 곱셈은 상관이 없을 수 있지만 나눌 때는 순서가 중요하므로 유의하자!

 

 

✨ 코드

N = int(input())
case = list(str(input()))
alpha2num = []
dict = {}

for i in range(N):
    dict[chr(i+65)] = int(input())

stack = []
temp = 0

for item in case :
    if item.isalpha():
        stack.append(item)
    else :
        if len(stack)==0 :
            print(0)
            break
        else :
            y = stack.pop()
            if y in dict :
                y = dict[y]
            x = stack.pop()
            if x in dict :
                x = dict[x]
            
            if item == '+':
                stack.append(x+y) 
            elif item == '-':
                stack.append(x-y) 
            elif item == '*':
                stack.append(x*y) 
            elif item == '/':
                stack.append(x/y) 
                
print("{:.2f}".format(stack.pop()))