백준 1935 후위 표기식2 ( stack )

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

1935번: 후위 표기식2

이런 식으로 후위표기 계산을 해야하는 문제..

우선 후위표기식이 어떻게 계산되는가를 아는것이 중요했다.

후위표기식은 앞에서부터 괄호를 만들어가면서 왼쪽 두 수에 오른쪽 기호를 대입해 계산해나가는 방식.

예제는 A + ( B * C ) / ( D - E ) 이런 식으로 나타낼 수 있다.

어떻게 계산하는지 알고 난 후 이를 어떤 식으로 묶어서 계산해나가야할지 막막했는데 스택을 이용하라는 힌트가 있었다.

그렇게 생각하고 나니 숫자가 들어올 때마다 스택에 쌓고, 괄호가 들어오면 맨 위 두 숫자끼리 계산을 한 뒤에 다시 집어넣는 식으로 계산하면 되지 않을까? 라는 생각이 들었고 이를 코드로 전환시켰다.

N = int(input())
post = input()
nlst = []
dic = {}
stack = []
for i in range(N):
    nlst.append(int(input()))
for i in range(len(post)):
    if 'A' <= post[i] <= 'Z':
        dic[post[i]] = nlst[ord(post[i]) - ord('A')]
        stack.append(dic[post[i]])
    elif post[i] == '+':
        stack.append(stack.pop() + stack.pop())
    elif post[i] == '-':
        stack.append((-stack.pop() +stack.pop()))
    elif post[i] == '*':
        stack.append(stack.pop() * stack.pop())
    elif post[i] == '/':
        temp = stack.pop()
        stack.append(stack.pop() / temp)
print(format(stack[0], ".2f"))

이것이 내가 짠 코드이다. 더 간단한 방법도 있을 테지만 우선은...

입력값은 N, post, nlist 순이고

1.맨 처음에 nlist를 채운 뒤에

2.post라는 입력한 문자열의 길이만큼 하나씩 내려가면서 A~Z일 때는 딕셔너리에 정리함과 동시에 stack에 넣어주었다.

여기서 딕셔너리를 쓴 이유는 같은 문자는 같은 숫자로 보기 때문이다.

파이썬에서는 ord('A')이런 식으로 해줘야 char를 int로 전환한 값이 나온다고 한다.

그렇게 해서 A~Z이 각각 인덱스 0~25의 고유의 값을 dictionary에 저장해나갈 수 있게 된다.

3.그렇게 해서 저장된 딕셔너리의 '값'을 stack에 넣어주면 알파벳에 해당되는 값들만 stack에 저장이 된다.

4.만일 알파벳이 아닌 기호가 오면 각각 stack의 맨 위의 값과 그 아래의 값에 대한 연산을 실행해준다.

순서가 상관없는 +, *와 같은 경우는 그냥 연산해주면 되지만 - /일 경우에는 순서가 중요하므로 뒤의 pop을 temp에 저장하거나 하는 식으로 세운다.

4.마지막으로 소수점 둘쨰자리까지 출력하는 방법은 print(format(숫자, ".2f"))이다. 잘 외워두자.