관리 메뉴

즐겁게, 코드

BOJ 1935번 - 후위 표기식 2 본문

💯 알고리즘/백준 온라인 저지

BOJ 1935번 - 후위 표기식 2

Chamming2 2021. 4. 14. 16:22

[백준 온라인 저지 링크]

 

1935번: 후위 표기식2

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이

www.acmicpc.net

시작하기 전, 후위 표기식이란 피연산자 뒤에 연산자가 오는 방식을 의미합니다.

다음은 테스트케이스로 주어진 예시의 계산 순서입니다.

 대충 후위 표기식에 대해서는 이해가 되셨다면, 눈썰미가 빠른 분들은 한가지 눈치채신게 있으실 겁니다.

이 문제는 스택에 수를 하나씩 넣으면서(push) 연산자를 만나면 이전 두 수를 빼고(pop), 연산을 수행한 값을 다시 스택에 넣으면 됩니다.

 

그럼 남은 문제는 후위 표기식 문자열의 알파벳을 주어진 숫자 입력에 어떻게 대응시키냐인데, 간단하죠!

표기식을 순회하며 만나는 문자가 알파벳이라면 numbers 배열 중 ["알파벳의 아스키 코드" - 65]번 인덱스에 대응하는 원소를 스택에 넣으면 됩니다. 만약 만나는 문자가 연산자라면, 스택에서 pop 연산을 두 번 수행한 후 주어진 연산자의 연산을 수행한 결과를 푸쉬합니다!

 

[정답 코드 - Python]

T = int(input())
S = input()
number_stack = []
operator_stack = []
numbers = []

for i in range(T):
    numbers.append(int(input()))

for i in S:
    if 'A' <= i <= 'Z':
        number_stack.append(numbers[ord(i) - 65])
    else:
        a = number_stack.pop()
        b = number_stack.pop()
        if i == "+":
            number_stack.append(a + b)
        if i == "-":
            number_stack.append(b - a)
        if i == "*":
            number_stack.append(a * b)
        if i == "/":
            number_stack.append(b / a)

print(format(*number_stack, ".2f"))

Tip 1. 문자를 아스키로 바꿔주는 ord 함수와 아스키를 문자로 바꿔주는 chr 함수를 헷갈리지 말아주세요!

Tip 2. 파이썬에서는 format 이라는 함수를 활용해 포맷화된 출력을 구현할 수 있습니다!

반응형
Comments
소소한 팁 : 광고를 눌러주시면, 제가 뮤지컬을 마음껏 보러다닐 수 있어요!
와!! 바로 눌러야겠네요! 😆