[백준] 1918 후위표기식 Python - 자료구조 시간에 나온 stack 과제

1일 1솔 벌써 49일 시간이 참 빠르다 ..!!  

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

1918번: 후위 표기식

 

중위 표기식을 후위표기식으로 바꾸는 문제이다 

1. 피연산자 인 경우 : 알파벳인지 아닌지는 isalpha() 함수로 간단히 확인할 수 있다. 파이썬은 짱이다

2. 연산자의 경우 : 우선순위에 따라 stack에서 빼낼지, 여부가 결정된다 

우선순위는 (  왼쪽 괄호  *, / 곱셈 나눗셈  -,+ 뺄셈 덧셈  순으로 높다 

( 가 나오면 우선순위가 가장 높으므로 일단 스택에 쌓는다 

/ 혹은 * 가 나오면 이와 같은 우선순위에 있는 /, * 연산자를 모두 스택에서 pop 하여 결과 문자열에 더한다. 

+, - 는 가장 우선순위가 낮으므로, +, - 보다 높은 우선순위를 가진 연산자들을 스택에서 pop하여 모두 문자열에 추가한다.  

) 가 나오면 스택에 쌓인 ( ~ ) 사이 연산자들을 모두 pop 하여 문자열에 추가한다 단, 후위표기식에서는 ()를 표기하지 않으므로 마지막으로 한번 더 pop 하여 ( 까지 제거해주어야 한다. 

 

for문의 순회가 끝난 후 stack에 남아있는 연산자들을 result 뒤에 append해주면 된다. 

 

data = input()
stack = []
result = ''

for now in data:
    if now.isalpha(): # 피연산자인 경우
        result += now   # 바로 결과로 출력해준다
    else:
        if now == '(':
            stack.append(now)
        elif now == '*' or now == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                result += stack.pop()
            stack.append(now)

        elif now == '+' or now == '-':
            while stack and stack[-1] != '(':
                result += stack.pop()
            stack.append(now)

        else: # ')' 인 경우
            while stack and stack[-1] != '(':
                result += stack.pop()
            stack.pop() # '(' 도 빼주어야 한다

while stack:
    result += stack.pop()
print(result)