파이썬 알고리즘 문제풀이 입문] 자료구조 활용 (스택, 큐, 해쉬, 힙) - 후위표기식 만들기 (스택)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

중위표기식이 입력되면 후위표기실으로 변환하는 프로그램을 작성하세요.
중위표기식은 우리가 흔히 쓰는 표현식입니다. 즉 3+5와 같이 연산자가 피연산자 사이에 있으면 중위표기식 입니다.
후위표기식은 35+와 같이 연산자가 피연산자 뒤에 있는 표기식 입니다.
ex) 3+5*2 → 352*+

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

e = input().rstrip()
stack = list()
result = ""

for i in e:
    if i.isdecimal():
        result += i
    else:
        if i == '(':
            stack.append(i)
        elif i=='*' or i=='/':
            while stack and (stack[-1]=='*' or stack[-1]=='/'):
                result += stack.pop()
            stack.append(i)
        elif i=='+' or i=='-':
            # 괄호 안의 것들 출력
            while stack and stack[-1]!='(':
                result += stack.pop()
            stack.append(i)
        elif i == ')':
            # 여는 괄호를 만날 때까지 pop
            while stack and stack[-1] != '(':
                result += stack.pop()
            stack.pop()

# 다 처리하고도 남은 것이 있을 때
while stack:
    result += stack.pop()

print(result)

- 먼저 숫자인지 아닌지로 판단한다. (isdecimal() 사용)

- 그 다음에 고려해야 할 사항 순서는 아래와 같다.

  ( (여는괄호) → *, / (곱하기, 나누기) → +, - (더하기, 빼기) → ) (닫는괄호)

- 곱하기,나누기가 더하기,빼기보다 먼저인 이유는 계산할 때 우선순위가 높기 때문이다.

- 다 처리하고도 남은 경우까지 생각해줘야 한다.