Algorithm - 후위 표기식 연산(스택)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[후위 표기식 연산]

 

후위 연산식이 주어지면, 연산한 결과를 출력하는 프로그램을 작성하시오.

예를 들어, 중위 연산식 3*(5+2)-9을 후위 연산식으로 표현하면 352+*9-이 되고 후위 연산식의 연산 결과는 12가 된다.

 

 

*입력 설명

첫 번째 줄에 후위 연산식이 주어진다. (연산식의 길이는 50을 넘지 않음)

연산식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다.

 

*출력 설명

연산한 결과를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys 
sys.stdin = open('AA/input_35.txt', 'rt')

a = input()
stack = []

for x in a:
    if x.isdecimal():
        stack.append(int(x))
    else:
        if x == '+':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 + n1)
        elif x == '-':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 - n1)
        elif x == '*':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 * n1)
        elif x == '/':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 / n1)
print(stack[0])

# 출력 : 12

 

input_35.txt(입력)

352+*9-

 

 

중요내용

1. 후위 연산식은 연산자 앞의 두 숫자를 연산에 반복 적용하는 방식으로 계산한다.
2. 즉, 입력 값으로 받은 후위 연산식에서 숫자는 리스트에 저장하고 연산자의 경우에는 리스트에서 최신 데이터 2개를 추출하여 연산을 적용한 후 연산의 결과 값을 다시 리스트에 저장하는 방식이다.
3. 이러한 연산 방식을 반복 실행하여 후위 연산식의 연산을 실행한다.
4. if절에서 append() 함수의 인자가 int(x)인 이유는 입력 값으로 받은 연산식이 문자열 자료형이기 때문이다.
5. 즉, 해당 입력 값을 리스트에 저장하고 이후에 추출하여 연산하기 위해서는 입력 값을 저장할 때 숫자형으로 형 변환을 해야한다.
6. if절과 elif절의 연산식에서 n2가 n1보다 먼저 나오는 이유는 연산을 할 때 리스트에서 추출한 순서를 지키기 위함이다.