[백준] 1935: 후위 표기식 2

안녕하세요.

이번 문제는 백준 1935번 후위 표기식 문제입니다.

실버 3단계 문제입니다.

 

비교적 간단하지만, 후위연산자에 대한 개념을 알아야 합니다.

후위 연산자는 저도 이번 문제를 통해서 처음 봤습니다.

 

검색해보니 기존 인간이 푸는 방식인 중위 연산자 방식과 다르게(A+B) 컴퓨터가 계산하기 수월한 방식인 후위 연산 방식이더라구요(AB +). 아마 조금만 검색해보시면 생소하지만 다들 이해 되실거라고 생각합니다.

 

그리고, 문자열 처리에 대해 알아야 하는 지식들이 있었습니다.

 

- ord: 특정 문자열을 해당하는 유니코드 정수로 변환

- eval: 문자열 식을 코드상에서 실행

- f string에서의 소숫점 처리 (아래 코드는 두번째 자리까지 표현)

  print(f"{value:.2f}")

 

이것 이외에는 후위 연산자를 직관적으로 푸는 문제라 자연스럽게 스택 사용을 하게 되고, 어려운 부분은 없습니다.

 

알고리즘 캔버스

아이디어

브레인스토밍

• 일단 후위표기식이란 무엇인지?
  • 중위표기식과 다르게 연산자가 뒤에 있는 방식
  • ABC*+DE/-
• stack을 이용해서 풀면 될 듯.

아이디어

1. n을 입력받는다.
2. 후위 표기식(= notation)을 입력받는다.
3. n개의 피연산자에 대응하는 값을 num 배열에 저장한다
4. stack 배열을 초기화한다
5. notation의 len만큼 for문을 돈다.
   1. 알파벳을 만나면
      1. num 배열에서 해당하는 숫자를 가져와 stack에 넣는다.
   2. 기호를 만나면 (무조건 stack이 있음)
      1. stack의 뒤에서부터의 두개를 가져온다. (2개 pop)
      2. eval을 통해 두개의 수를 연산한 값을 stack에 추가한다.
6. 0번째 값을 꺼내 f string으로 두번째 자릿수까지 잘라서 리턴한다.

시간 복잡도 (Big-O)

• O(N)

Code

import sys
input = sys.stdin.readline

n=int(input().rstrip())
notations=input().rstrip()
nums=[int(input().rstrip()) for _ in range(n)]
stack=[]

for i in range(len(notations)):
	if notations[i].isalpha():
		stack.append(nums[ord(notations[i])-ord("A")])
	else:
		b=stack.pop()
		a=stack.pop()
		r=eval(f"{a}{notations[i]}{b}")
		stack.append(r)
		
print(f"{stack[0]:.2f}")