[백준] 1918 후위 표기식 python 알고리즘 문제

문제 1918. 후위 표기식

 

1. 나의 코드와 발상 과정

최근 자료구조 공부를 하다가 기본 자료구조인 스택을 배웠는데, 대표적인 활용 예시로 괄호와 계산기에 적용을 연습하였다. 

연산자와 피연산자, 이항연산자, 단항연산자, infix 수식, postfix 수식을 알 수 있었는데, infix 수식에서 postfix 수식으로 바꿀 때, 연산자 스택과 피연산자 스택을 따로 두고 섞어 담아 출력하면 postfix 수식이 된다는 것을 알 수 있었다.

 

그 기억을 살려 아래와 같이 두 개의 스택을 놓고 코딩을 진행했다.

---

n = list(input())
stack = []
outstack = []
operator = {'(' : 0, '+' : 1, '-' : 1, '*' : 2, '/' : 2}
for i in n:
    if i in '+-/*':      
        while True:
            if len(stack) == 0:
                stack.append(i)
                break
            elif operator[stack[-1]] < operator[i]:
                stack.append(i)
                break
            else:
                outstack.append(stack.pop())
    elif i == '(':
        stack.append(i)
    elif i == ')':
        while stack[-1] != '(':
            outstack.append(stack.pop())
        stack.pop()
    else:
        outstack.append(i)

while len(stack) != 0:
    outstack.append(stack.pop())
print(''.join(outstack))

괄호의 경우에 출력이 되는 것이 아니기 때문에 쌍이 맞는 오른쪽 괄호가 나올 경우 쌍이 맞는 괄호가 나올때 까지 pop하여 피연산자가 있는 스택에 연산자를 append하는 방식으로 하나의 스택을 만들어 갔다.