1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
스택
- 선입후출 방식
- 후위 표기식, 가장 큰 수 등 이전에 사용한 데이터를 이용하여 해결할 때 가장 사용을 많이 하는 자료구조다.
- 연산자와 숫자 구분, 스트링 객체들을 차례로 저장하는 문제 등에 구분하거나 전 데이터를 이용한다.
- 파이썬의 경우 스택 또는 큐는 리스트의 인덱싱[-1] 과 pop(), popleft() 등을 통해 구현이 가능해서 리스트를 쓴다.
예제) 후위표기식 만들기(스택)
중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요.
중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 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-
구현(파이썬)
fomula = input()
stack = []
# 파이썬은 스트링을 더할 수 있다.
res = ''
# 더하기와 뺴기는 스택에 넣어두고 숫자는 그대로 출력
# 곱하기와 나누기를 만났으면 스택에서 곱하기와 나누기만 꺼내야한다.
# 없으면 곱하기 혹은 나누기를 넣는다.
# 여는 괄호가 나왔으면 일단 스택에 넣고
# 닿는 괄호가 나올 때 여는 괄호 전의 연산자들을 우선순위를 통해 pop()한다.
# 즉 여는 괄호 뒤에 연산자를 만나면 여는 괄호 뒤에 들어간 연산자를 연산처리한다.
# 여는 괄호 뒤에 연산자가 없으면 그냥 현재를 넣는다.
# 우선순위가 높은 연산자를 스택의 상단에 위치시키는게 핵심이다.
# 기본적으로 연산자면 자기 순서도 append 한다는 것을 잊지 말자
for x in fomula:
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)
