2023. 10. 5. 00:00ㆍ알고리즘(python)/자료구조
접근
처음 설명에 나와있는대로 식이 주어질때 식에 괄호를 치고 연산자를 빼낼생각을 했다. 하지만 이렇게 구현할 생각을 하니 연산자를 빼낼 때 관호의 개수도 세면서 너무 코드가 복잡해지고 시간복잡도도 매우 안좋을거같다고 생각했다. 두 번째로 생각한 방법은 알파벳과 연산자를 따로 모아 이를 더해서 결과를 만들어낼 생각을 했다. 시간복잡도와 구현면에서 매우 좋을거같아서 이방법을 깊게 생각하기 시작했다.
일단 괄호를 생각하면 너무 복잡해서 괄호 없이 생각했다.
1.A*B+C+D
(((A*B)+C)+D)
AB*C+D+
2.A+B+C*D
((A+B)+(C*D))
AB+CD*+
3.A+B*C*D
(A+((B*C)*D))
ABC*D*+
4. A+B-C+D
(((A+B)-C)+D)
AB+C-D+
5. A+B*C+D
((A+(B*C))+D)
ABC*+D+
1. 동일한 연산 기호가 바로전에 있을때.
-> 기존에 있는걸 빼서 붙이고 새로운걸 넣는다.
2. 더 낮은 우선순위의 연산 기호가 바로전에 있을때.
-> 기존에 있는걸 안빼고 같이 넣는다.
3. 기존에 높은 우선순위의 연산 기호가 바로전에 있을때.
->기존에 있던걸빼고 새걸 넣는다.
4. 끝나면 그냥 모아뒀던걸 뺀다.
-> 뺄때 들어온순으로 빼야하니 스택을 사용
이렇게 하고 생각이든건 괄호도 어떠한 연산이라고 생각해서 2번 조건처럼 기존에 있는걸 안뺀 상태로 넣고 3번 조건을 변형해서 기존에 있는걸 빼는게 원칙이지만 안빼고 그대로 넣고 기존 규칙대로 하다가 )가 나오면 짝을 찾아 (까지 비워준다.
5.A+(B+C+D)+F
((A+((B+C)+D))+F)
ABC+D++F+
나의 코드
import sys
input = sys.stdin.readline
st = list(input().strip())
one = set(["*","/"])
two = set(["+","-"])
symbol = []
result = ''
for s in st:
if s.isalpha():
result +=s
else:
if s in one:
while symbol and symbol[-1] in one:
result+= symbol.pop()
symbol.append(s)
elif s in two:
while symbol and symbol[-1] != '(':
result+= symbol.pop()
symbol.append(s)
else:
if s == '(':
symbol.append(s)
if s == ')':
while symbol and symbol[-1] != '(':
result+= symbol.pop()
symbol.pop()
while symbol:
result+= symbol.pop()
print(result)