[백준] 1918번 후위 표기식 - 파이썬(Python)

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

문제

 

접근법

 

###검색해서 풀었기에, 다음에 다시 해보기

 

처음에는 무조건 괄호가 주어지는 줄 알고 짰는데 계속 틀렸다 나와서 찾아보니 괄호가 없이도 자체 수식에서 다 후위 연산자로 바꿨어햐 했다.

 

근데 그걸 아니, 계속 생각해도 알고리즘의 가닥이 안잡혀서 결국 알고리즘을 찾아보게 되었다.

 

연산자에 우선순위를 매겨 스택의 마지막보다 우선순위가 높은 연산자는 스택에 append하고

스택의 마지막과 우선순위가 같거나 낮으면 스택의 마지막을 pop하고 현재는 append 하는 알고리즘을 적용했다.

 

연산자 우선순위

1. '*' 또는  '/'

2. '+' 또는 '-'

 

[주요 변수]

arr (list) : 중위 연산식

ops (list) : 연산자 넣을 곳

ans : 변경된 후위 연산식

 

[과정]

1. 입력받은 arr을 처음부터 하나씩 읽기

2. 피연산자일 땐 그대로 ans에 저장

3. '('일때도 그대로 ans에 저장

4. ')'이면 (가 나올때까지 ops에서 pop해서 ans에 저장하고 '('도 pop

5. '+' 또는 '-'가 나오면 ops의 마지막이 '('일 때까지 pop해 ans에 저장하고 현재 값은 append

6. '*' 또는 '/'가 나오면 ops의 마지막이 '*', '-'인 동안 pop해 ans에 저장하고 현재 값은 append

7. arr 마지막까지 돌리면 ops의 나머지 전부 pop해서 ans에 입력

 

 

코드

arr=input()
ops=[]
ans=''

for i in arr:
    if i.isalpha():
        ans+=i

    elif i=='(':
        ops.append(i)

    elif i==')':
        while ops and ops[-1]!='(':
            ans+=ops.pop()
        ops.pop()

    elif i=='+' or i=='-':
        while ops and ops[-1]!='(':
            ans+=ops.pop()
        ops.append(i)

    elif i=='*' or i=='/':
        while ops and (ops[-1]=='*' or ops[-1]=='/'):
            ans+=ops.pop()

        ops.append(i)

while ops:
    ans+=ops.pop()

print(ans)