[백준] 1918 파이썬(python) : 후위 표기식

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

1918번: 후위 표기식

 

 

import sys
string = list(sys.stdin.readline().rstrip())
res = '' #1
stack = [] #2
for char in string:
    if char.isalpha(): #3
        res += char
    else:
        if char == '(': #4
            stack.append(char)
        elif char == '*' or char == '/': #5
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(char)
        elif char == '+' or char == '-': #6
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.append(char)
        elif char == ')': #7
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack: #8
    res += stack.pop()
print(res)

 

#1, 2 : 결과 문자열과 stack 리스트 같이 초기화

#3 : 입력값이 피연산자이면(알파벳이면) 결과 문자열에 추가

#4 : 여는 괄호가 입력되면 stack에 추가

#5 : *와 / 연산자는 우선순위가 높아 괄호에서도 먼저 빠져나간다. 그래서 stack의 top에 자신들과 같은 연산자가 있으면 빼서 결과 문자열에 추가해준다.(우선순위가 같으면 앞에 있는 연산자가 먼저 계산되므로) 그리고 반복을 끝내면 stack에 자신을 넣는다.

#6 : +와 - 연산자는 우선순위가 낮아 괄호에서 나중에 빠져나간다. 그래서 stack의 top에 우선순위를 높혀주는 (과 나오기전까지 빼서 결과 문자열에 넣어준다. 그리고 자신은 stack에 넣는다.

#7 : 닫는 괄호는 여는 괄호가 나올때까지 모두 빼서 결과 문자열에 넣는다. 그리고 여는 괄호도 빼준다.

#8 : stack에 남은 문자열이 없을때까지 결과 문자열에 넣어준다.

 

대학교 자료구조 시간에 후위연산자 구현에서 배웠던 내용을 파이썬으로 다시 구현한것 같다. 

 

문자열 배열과 stack 배열 두 가지를 이용해서 해결한점은 다른 문제들과 비슷한것 같다. 어려웠다.