25. 후기표기식2(1935), 후기표기식(1918)

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

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

답:

n = int(input())
word = input()                # 후위표기식을 word에 저장함
num_lst = [0]*n				  # 피연산자값을 저장하기 위한 num_lst 생성	

for i in range(n):
    num_lst[i] = int(input())  # 피연산자값 받기

stack = []                    # stack 리스트를 통해 후위표기식 계산

for i in word :					
    if 'A' <= i <= 'Z' :		# 후위표기식에서 알파벳을 만나면 stack에 저장한다.
        stack.append(num_lst[ord(i)-ord('A')])
    else :						# 연산자를 만나면
        str2 = stack.pop()		# stack 리스트의 마지막 2항목을 꺼내와서 계산한다.
        str1 = stack.pop()

        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' % 함수를 통해 소수점 자릿수를 제한한다.

 

후위 표기식이 무엇인지 알고 싶다면 "후위 표기식" 문제를 먼저 풀어야 한다. 그래서 뒤에 서술할 "후위 표기식" 문제를 먼저 읽고 오는 것을 추천한다.

---

후위 표기식 특성상 연산자가 등장하면 앞의 피연산자들을 뒤부터 계산하는 방식을 알고 있어야 한다.

이후 경우의 수를 나누어서 풀어야 한다.

후위표기식의 개념을 정확히 파악하고 stack 리스트에 알파벳이 아니라 피연산자의 값으로 저장해야함을 알면 쉽게 풀리는 문제이다. (모르면 안 풀림.)

 i가 알파벳인지 파악을 위해 'A'<=i<='Z' 사용한다. num_lst라는 빈 리스트로 피연산자값을 받는다.

이후 소수점 두번째자리로 출력을 해줘야 하기에 %. 2f를 써야 한다. 

---

문제.
수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.
이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다.

예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.
예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.
다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

답:

n = list(input())
stack=[] #데이터를 저장해주는 스택
res='' #출력할 변수
for s in n:
    if s.isalpha(): #알파벳을 구별해주는 함수 
        res+=s
    else:
        if s == '(':
            stack.append(s)
        elif s == '*' or s == '/':
            while stack and (stack[-1] == '*' or stack[-1] =='/'):
                res += stack.pop()
            stack.append(s)
        elif s == '+' or s == '-':
            while stack and stack[-1] != '(':
                res+= stack.pop()
            stack.append(s)
        elif s == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack :
    res+=stack.pop()
print(res)

후위 표기법을 설명해주었던 문제이다. 사실 후위 표기법 2보다는 먼저 풀어야 하는 문제이지만, 알고리즘 기초 1/2의 순서로 풀어서 티스토리에는 2가 먼저 기입이 되었다.

그래서 먼저 이 문제를 풀었지만 기록은 뒤에 나오게 되었다.

아무튼, 후위 표기식은 말 그대로 "연산자 표기법"을 뒤에 작성해주는 것이다.

이를 구현하기 위해서는 "스택"을 이용해서 데이터를 통제해줘야 한다.

그래서 n을 기입받고 stack이라는 빈 배열을 만들어준다. 출력은 res가 되어줄 것이다.

그리고 이 문제를 풀고 싶다면, 사칙연산의 우선순위에 대해서 알아 둬야한다.

문제에서는 +, -, *, /, (, )와 알파벳 대문자만 사용한다.

우선순위는...

1. ( , )

2. * , /

3. + , -

가 된다. 그리고 같은 우선순위에 있는 연산자의 경우 왼쪽의 연산자부터 처리하면 된다.

문제에서는 알파벳을 사용하므로 

isalpha() 메서드를 사용해서 알파벳을 구분한다.

알파벳이 들어오면 결괏값 문자열에 추가해 주고

연산자가 들어오면 우선순위에 맞게 처리를 해준다.

(우선순위는 위에서 말했음)