[백준] 1935 후위표기식 (python)

1) [백준] 1935 후위표기식 (python) 

문제 출처 : 

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

 

2) 문제

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

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

 

특정 리스트 stack 에 피연산자의 값을 저장하고 연산자를 pop함수를 통해 끄집어와서 계산 하는 방식

 

슈도코드 

입력 : n,word,num_lst
n = 정수로 입력받기
word = 문자열로 입력받기
num_lst = 크기가 n인 리스트

각 피연산자 값 입력 받기 :
반복 횟수 : n
	num_lst[i] = 정수로 입력받기
스택 초기화 :
stack = 빈 리스트

후위 표기식 계산 : 
반복 횟수 : word 에 각 문자 i 에 대해
	만약 i가 알파벳 대문자 (A-Z) 이면 :
    	피연산자 값을 스택에 추가 : stack.append(num_lst[알파벳의 인덱스])
    그렇지 않으면 (i는 연산자) :
    	str2 = 스택에서 마지막 항목 꺼내기
        str1 = 스택에서 마지막 항목 꺼내기
        
        연산자에 따라 계산하여 결과를 스택에 추가 :
        만약 i가 '+' 이면 :
        	stack.append(str1+str2)
        만약 i가 '-' 이면 :
        	stack.append(str1-str2)
        만약 i가 '*' 이면 :
        	stack.append(str1*str2)
        만약 i가 '/' 이면 :
        	stack.append(str1/str2)
 결과 출력 : 
 결과 값 = stack 의 첫번째 항목
 소수점 이하 2자리까지 출력 : 결과값을 '%.2f'형식으로 출력

 

 

 

3)소스  코드

 

import sys

n = int(sys.stdin.readline().rstrip())
word = sys.stdin.readline().rstrip() #후위 표기식을 word 에 저장
num_lst = [0] * n #피연산자값을 저장하기 위한 nun_lst

for i in range(n) :
    num_lst[i] = int(sys.stdin.readline().rstrip()) #피연산자값 받기

stack = []

for i in word :
    if 'A' <= i <= 'Z' : #후위표기식에서 알파벳을 만나면
        stack.append(num_lst[ord(i)-ord('A')]) #알파벳 대문자를 0부터 시작하는 인덱스로 변환
    else : #연산자를 만나면
        str2 = stack.pop()
        str1 = stack.pop() # stack 리스트의 마지막 2항목을 꺼내와서 계산

    if i == '+' :
        stack.append(str1+str2)
    elif i == '-' :
        stack.append(str1-str2)
    elif i == '*' :
        stack.append(str1*str2)
    elif i == '/' :
        stack.append(str1/str2)
print('%.2f' %stack[0]) #'%.2f' 함수를 통해 소숫점 자릿수 제한

 

 

TIL

 

1. 스택에 넣기

2. 후위표기식(postfix notation)

일반적인 중위 표기식(infix notation) 과 달리 연산자를 피연산자 뒤에 표기하는 형태

후위 표기식이 경우 연산자 우선순위를 명시적으로 표현할 필요가 없어진다. 연산자와 피연산자 사이의 순서가 

명확하게 정해져 있기 때문에 괄호를 사용하여 연산자의 우선순위를 지정할 필요가 없다.

후위 표기식은 스택을 자주 이용한다.

1. 수식을 왼쪽에서 오른쪽으로 한 문자씩 읽는다.

2. 만약 읽은 문자가 피연산자라면 해당 값을 스택에 push

3. 만약 읽은 문자가 연산자라면, 스택에 필요한 개수의 피연산자를 Pop해서 해당 연산 수행하고 연산 결과를 push

4. 수식 다 처리하면 스택에는 최종 결과

 

'3 4 + '

3push

4push

+ 4와 3 pop 덧셈 수행 결과 7 push