BOJ 1918: 후위 표기식- 파이썬(Python)

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

<접근 방법>

주어진 수식을 후위 표기식으로 변환하는 문제이다. 우선 "후위 표기식"이 무엇인지 알아보자.

 

후위 표기법은 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다. 예시로 아래의 그림의 수식을 후위 표기식으로 변경해 보자.

후위표기식으로 변환하는 방식

그림에 나와있는 화살표로 연산자를 이동시키면 "ABC*+DE/-"가 변환 결과가 된다.

 

해당 문제는 대표적인 "스택으로 해결할 수 있는 문제"이다. 그렇다면 스택을 어떻게 적용해야 해결할 수 있는지 확인해 보자. 우선, 가장 간단한 형태의 수식인 $A+B$ 로 시작해 보자.

 

초기 상태는 아래 그림처럼 "input", "stack", "result"로 구성할 수 있을 것이다. 이제 input의 index 순서대로 변환 과정을 진행해 보자.

A+B를 변환하기 위한 초기 설정

 

"A"의 경우, stack에 넣지 않고 바로 result에 삽입한다. 왜냐하면 후위 표기식은 연산자를 뒤로 보내는 과정이기 때문이다.

A는 바로 result에 삽입해야 한다.

"+"는 연산자이다. 그러므로 Stack의 제일 윗부분(지금 상황에서는 index 0)에 삽입한다.

 

B도 피연산자이므로 A에서 진행한 연산과 동일하게 진행한다.

이제 input 순회는 모두 마쳤다. 그럼 마무리로, Stack에 저장되어 있는 연산자들을 "stack 순서대로" 제거하면서 result 뒤에 붙여주면 "AB+"가 되고 후위 표기식 변환이 완료된다.

 

하지만 수식은 간단한 것만 존재하지 않는다. 이제 "연산 우선순위"를 어떻게 처리해야 할지 알아보자. 우선 아래에 제시한 수식을 이용해 보자.

 

$$A-B+C$$

 

해당 식에 사용한 연산자는 같은 우선순위를 가지고 있다는 것을 알 수 있을 것이다. 그렇다면 위의 연산 방식을 그대로 사용하면 틀린 답인 "ABC+-"가 나올 것이다. 하지만 정답은 "AB-C+"이다. 어떻게 처리해야 맞는 답을 처리할 수 있을까?

 

우선, A-B 까지는 위에서 사용한 방식을 그대로 적용할 수 있다. 이제 +의 차례에서는 어떻게 처리해야 할까?

 

 

+와 -의 우선순위는 같으므로, 수식 연산은 순차적으로 이루어지게 될 것이다. 그렇다면 stack에 있는 - 연산자를 result에 삽입하고 +를 stack에 넣어주면 된다.

 

 

이후에 마지막까지 처리를 진행하면 "AB-C+"가 나올 것이고, 이는 실제로 맞는 변환이다.

 

지금까지는 +와 - 사이처럼 "연산자 우선순위가 같은" 연산자 간의 처리를 알게 되었다. 하지만 연산자는 *와 /처럼 연산자 우선순위가 높은 연산자들도 존재한다. 이들에 대한 처리를 어떻게 해야 할지 알아보자. 이번에는 아래의 수식을 활용해서 분석해 보자.

 

$$A*B+C$$

 

해당 수식을 위에서 사용한 방법을 그대로 사용하면 "ABC+*"가 될 것이다. 하지만 이는 오답으로 실제 정답은 "AB*C+"가 되어야 한다. 왜냐하면 * 와 / 는 +와 - 보다 연산 우선순위가 높기 때문이다.

 

그렇다면 어떻게 처리해야 할까? 연산자의 차례가 되었을 경우에 stack의 맨 윗부분에서 특정 조건을 확인하면 해결할 수 있다.

 

그러면 특정 조건은 무엇일까? 직접 단계별로 따라가 보면서 확인해 보자.

 

A*B까지는 위에서 진행한 사항과 동일하게 진행하면 된다. 하지만 + 차례에서는 어떻게 연산자 우선순위를 반영하면서  처리할 수 있을까?

 

답은 간단하다. "Stack의 맨 위에 들어있는 연산자"가 "삽입되려는 연산자"보다 우선순위가 "낮다면" Stack의 윗 원소를 result 배열로 삽입해 주면 되는 것이다.

 

 

그 후에는 이전에 적용했던 연산을 그대로 적용하면 정답인 " AB*C+"가 나오게 된다.

 

 

그러면 이제 "괄호 처리"는 어떻게 적용해야 하는지 알아보도록 하자. 괄호가 있으면 "연산자 우선순위"에 상관없이 무조건 괄호 내부의 연산이 먼저 이루어져야 한다는 특징이 있다. 아래의 예시를 이용해서 어떻게 처리해야 하는지 살펴보도록 하자.

 

$$A*(B+C)$$

 

위의 예시와 비슷한 형태이지만 이번에는 괄호가 추가되었다. 위의 식을 변환하면 "ABC+*"가 되어야 한다.

 

A와 * 단계까지는 위의 연산과 동일하게 처리하면 된다. 하지만 괄호가 나오면 어떻게 처리해야 할까? 

 

우선, 괄호의 종류에 따라 다르게 처리를 진행해야 할 것이다. 여는 괄호일 경우에는 stack에 바로 삽입하고 다음 차례를 연산한다. 그 후에 닫는 괄호의 차례가 되었을 경우에 "여는 괄호가 있는 index 직전"까지 모든 연산자를 차례대로 result에 삽입해 주면 될 것이다.

 

그 후에는 이전에 진행했던 연산과 동일하게 처리하면 될 것이다.

 

결론적으로 위의 과정을 따라서 처리를 하면 답을 구할 수 있을 것이다.

<소스 코드>

위의 접근법을 이용하여 코드로 구현한 결과이다.

import sys

a = sys.stdin.readline().rstrip()
s = []
result = []

for i in a:
    if ord(i) >= ord('A') and ord(i) <= ord('Z'):
        result.append(i)
    elif i == '(':
        s.append(i)
    elif i == ')':
        top = s.pop()
        while top != '(':
            result.append(top)
            top = s.pop()
    elif i in "+-*/":
        if i == '*' or i == '/':
            if len(s) == 0:
                s.append(i)
            else:
                while True:
                    if len(s) <= 0 or s[-1] == '(' or s[-1] in '+-':
                        s.append(i)
                        break
                    else:
                        result.append(s.pop())
        else:
            if len(s) == 0:
                s.append(i)
                continue
            if s[-1] in "+-*/":
                while True:
                    if len(s) <= 0 or s[-1] == '(':
                        s.append(i)
                        break
                    else:
                        result.append(s.pop())
            else:
                s.append(i)
while s:
    result.append(s.pop())

print(('').join(result))