[Python Algorithm] 자료구조(스택) - 후위표기식 만들기

> 자료구조 활용 - 스택, 큐, 해쉬, 힙 (스택 편)

 

📖 문제 :  후위표기식 만들기

중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요.
중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 3+5 와 같이 연산자가 피연산자 사이에 있 으면 중위표기식입니다.
후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식입니다.
예를 들어 중위표기식이 3+5*2 를 후위표기식으로 표현하면 352*+ 로 표현됩니다.
만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면
(3+5)*2 이면 35+2* 로 바꾸어야 합니다.

※후위 표기식이 이해가 안되면 구글링으로 공부해보는 것도 좋습니다.

 

 

입력설명
첫 줄에 중위표기식이 주어진다. 길이는 100을 넘지 않는다. 식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다.

 

출력설명

후위표기식을 출력한다.

 

입력예제 1

3+5*2/(7-2)

 

출력예제 1

352*72-/+

 

입력예제 2

3*(5+2)-9

 

출력예제 2
352+*9-

 

import sys

s = input()
stack = []
result = ''
for x in s:
	if x.isdecimal():
    	result += x
    else:
    	if x=='(':
        	stack.append(x)
        elif (x=='*' or x=='/'):
            while stack and (stack[-1]=='*' or stack[-1]=='/'):
                result+=stack.pop()
            stack.append(x)
        elif (x=='+' or x=='-'):
            while stack and stack[-1] != '(' :
                result += stack.pop()
            stack.append(x)
        elif x==')':
        	while stack and stack[-1] != '(':
        		result += stack.pop()
			stack.pop()		# '('를 빼주기
while stack:
	result += stack.pop()
print(result)

⭐️ Point ! ⭐️

• 발생할 수 있는 경우들을 잘 구분짓기
  
  
• 연산자를 stack에 넣음.
  
  
• 조건식 만들기 [ 무조건 자기보다 우선순위가 같거나 높은게 있으면 다 빼서 result에 넣는데, 괄호에선 예외임 ]
  - '('일 경우 : 그냥 append
  - '*'나 '-'일 경우 : 이미 stack에 쌓여있는 연산자들 중, 자기랑 우선순위가 (크거나)같은 연산자 '*'와 '/'이 있을 경우 그것을 pop시키고, 그 값을 result에 넣어준 후, 자신이 들어감.
  - '+'나 '-'일 경우 : 자신보다 우선순위가 같거나 크므로 '('가 나오기 전까지 다 pop 시키고, 그 값들을 result에 넣어줌.
  - ')' 일 경우 : '('가 나올 때까지 다 pop을 시키고 result시켜줌. 왜냐하면 ()안에 있는 값들은 어떤 것들보다 우선순위가 높으니까 ! 그리고 그냥 result에 값을 넣지않고 pop만 시키는 값은 '('을 pop !

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이