[Python] 백준, 1918(스택)

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

1918번: 후위 표기식

친숙한 문제다. 예전에 프로그래머스 유료 강의('어서 와 자료구조 및 알고리즘은 처음이지?')를 수강하다가 스택의 연습 문항으로 나왔던 문제다. 당시에는 수업에서 해결 방향과 구조를 어느 정도 제시해주었기에 무감각하게 넘어간 기억이 있는데, 이렇게 만나니깐 등골이 서늘해지더라. 복습의 중요성을 한 번 다시 느꼈달까...

변명을 하자면 문제 해석에서 미스가 있었다.

예를 들어 a+b+c 의 후위 표기식은 abc++ 가 아니라, ab+c+ 다.

이 부분을 알아차렸어도 사실 바로 풀어내진 못했겠지만, 정답을 맞추는 과정이 조금은 덜 복잡했을 것 같다.



# PYTHON CODE (1)

import sys
 
s = list(map(str, sys.stdin.readline().rstrip()))
stk1, stk2 = [], []
c_list = ['+', '-', '/', '*', '(']
 
for i in s:
    if i in c_list:
        stk2.append(i)
    elif i == ')':
        while len(stk2) > 1:
            k = stk2.pop()
            if k == '(':
                if stk2[-1] == '*' or '/':
                    stk1.append(stk2.pop())
                break
            else:
                stk1.append(k)
    else:
        stk1.append(i)
 
print(*stk1)

근본도 없는 풀이다. 굿노트에 이것저것 끄적이면서 그럴싸하게 생각했지만, 이 문제에서 중요한 포인트는 연산자들 간의 우선순위다. while문 중간에 어떻게든 우선순위를 가리려는 노력은 보였지만, 그건 명확히 이 문제를 해석해서 작성한 코드라기보다는 무의식적으로 문제를 해결하려는 움직임인 것 같다.

또한 마지막 줄대로 결론을 내리면 정답들 간에 공백이 생겨서 join함수를 사용해야하며, 반복문이 끝나고 stk2에 남겨진 연산들에 대한 대책이 제시되어 있지 않다. 

 

방향은 얼추 잡았으나 좀 더 세심하게 접근하지 못한게 흠인 것 같다. (사실 오늘 집중이 잘 되지 않더라)

 

 

 

 

# PYTHON CODE (2)

import sys
 
s = list(map(str, sys.stdin.readline().rstrip()))
stk1, stk2 = [], []
dic1 = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
 
for i in s:
    if i == '(':
        stk2.append(i)
    elif i == '+' or i == '-':
        while stk2 and stk2[-1] != '(':
            stk1.append(stk2.pop())
        stk2.append(i)
    elif i == '*' or i == '/':
        while stk2 and dic1[stk2[-1]] == 3:
            stk1.append(stk2.pop())
        stk2.append(i)
    elif i == ')':
        while stk2:
            k = stk2.pop()
            if k == '(':
                break
            stk1.append(k)
    else:
        stk1.append(i)
 
while stk2:
    stk1.append(stk2.pop())
 
print(''.join(stk1))

 

이게 파이썬의 우수함일까 싶다.