알고리즘 기초 1/2 203-자료구조(참고): 후위 표기식

후위 표기식(python 1918)

사실 지금도 코드가 잘 이해안됨

infix = str(input())
stack = []
result = ''

for i in infix:
    if i == '(':
        stack.append(i)

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

    elif i == '*' or i == '/':
        while stack and (stack[-1] == '*' or stack[-1] == '/'):
            result = result + stack.pop()
        stack.append(i)

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

    else:
        result = result + i

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

모 블로그 설명 그대로 가져오기
코드를 찬찬히 살펴보자.
스택을 사용하는데, 이 스택에는 연산자와 괄호가 들어간다. 이를 활용해 표기할 순서를 정해준다. 만약 문자라면 바로 출력할 문자열에 넣어준다.
괄호 열림 문자 '('가 들어올 경우, 단순하게 추가만 시켜준다. 그리고 ')'가 들어온다면, 그로 인해 닫힌 식은 바로 계산해야 한다는 것을 뜻한다. 중첩된 괄호가 있을 때 가장 먼저 등장하는 ')'가 가장 안쪽 괄호를 담당하기 때문이다. 그래서 ')'가 나온다면 바로 그 안 속의 연산자들을 꺼내어 문자열에 넣어준다. 그리고 '('가 나오면 반복을 멈추고, '('는 깔끔하게 제거한다.
이외에 사칙연산이 들어올 때는 우선순위에 따라 조건을 달리 한다. 스택에서 먼저 연산될 놈이 먼저 나가야만 한다. 그렇지만 같은 우선순위라면 뒤엣놈이 나가야만 한다. 뒤엣놈이라는 것은 스택을 사용하는 것만으로 해결되고, 곱셈과 나눗셈은 스택에 들어간 녀석들을 바로 바로 꺼내주는 방식으로 활용한다. 만약 스택에 *가 들어간 상황에서 다른 연산자가 나온다면, 바로 *가 나와 문자열에 들어가고 그 자리에 다른 연산자가 들어가게 될 것이다. 하지만 이후 우선순위인 +의 경우에는 바로 튀어나오지 않는다. +가 스택에 들어간 상황에서 다른 연산자가 들어온다면? *가 들어온다면 스택은 pop되지 않을 것이다. 그 상태에서 *가 들어가게 되니 이로써 우선순위가 밀리는 것이 표현된다. 나중에 스택을 나올 때는 결국 *가 먼저 나오게 되니, +가 후순위로 밀려난 꼴이 된다.

그래서 결국 어떻게 된다는 것인가.. 괄호가 들어온 케이스에 대해서는 괄호가 닫힐 때마다 바로바로 처리해주고, 사칙연산의 경우에는 기본적으로 스택에 들어있던 것들을 다 빼내는 형식으로 작동하는데 이때 곱셈과 뺄셈이 우위를 가질 수 있도록 이전에 덧셈이나 뺄셈이 있었다면 그것을 꺼내지 않고 스택에 들어간다는 것. 위에서 말했듯이 괄호가 없는 이상에서는 피연산자는 길어봐야 3개밖에 연속으로 오지 못한다. 스택은 대체로 바로바로 비워진다는 것을 알 수 있다.