Algorithm - 후위 표기식 만들기(스택)

 

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

 

문제

[후위 표기식 만들기(스택)]

 

중위 표기식은 우리가 흔히 쓰는 표현식이다. 

 

예를 들어, 3+5와 같이 연산자가 피연산자 사이에 있으면 중위 표기식이다.

후위 표기식은 35+와 같이 연산자가 피연산자 뒤에 있는 표기식이다. 즉, 중위 표기식 3+5*2를 후위 표기식으로 표현하면 352*+로 표현된다. 만약 다름과 같이 연산 최우선인 괄호가 표현된 식이라면 (3+5)*2의 중요 표기식이 35+2*의 후위 표기식으로 바뀐다.

 

위의 예시를 참고하여 중위 표기식이 입력되면, 후위 표기식으로 변환하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 중위 표기식이 주어진다. (길이는 100을 넘지 않음)

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

 

*출력 설명

후위 표기식을 출력한다.

 

 

---

 

 

풀이(Python)

답안

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

a = input()
stack = []
res = ''

for x in a:
    if x.isdecimal():
        res += x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack:
    res += stack.pop()
print(res)

# 출력 : 352*72-/+

 

input_34.txt(입력)

3+5*2/(7-2)

 

 

중요내용

1. 중위 표기식을 후위 표기식으로 만드는 매커니즘은 입력 받은 연산식에서 숫자는 그대로 출력하고, 연산자는 우선 순위에 따라 리스트에 저장한 후 append() 함수와 pop() 함수를 활용하여 후위 표기식을 완성하는 방식이다.
2. isdecimal() 함수는 해당 데이터가 숫자형 데이터인지를 알려준다.
3. 변수 res에 후위 표기식의 결과를 누적하여, 마지막에 표기식 전체를 출력한다.
4. 참고로, 후위 표기식의 연산 매커니즘은 연산자 앞의 두 숫자를 연산에 적용하여 해당 결과를 도출하는 방식이다.