[python] 백준 1918 - 후위표기식

백준 1918 - [Gold 2]

쉬운 문제 ?

정보처리기사에서도 Tree 자료구조를 다룰 때 후위 표기법과 트리의 후위 순회 등을 볼 수 있다.

골드 2 문제치고는 쉬운 편인 것 같다.

후위 표기법과 stack을 사용할 수 있다면, 금방 풀 수 있다.

SSAFY에서도 알고리즘 학습 주간에 tree 개념에 들어가기 전,

stack 자료구조를 배울 때 푸는 문제 중 하나였다.

배울 당시에는 10분도 안 걸려서 풀었는데,

이번에는 3시간 넘게 잡고 있다가 결국 못 풀고

과거의 나에게 달려가 코드 제출 내역을 확인했다.

심지어 그걸 보면서도 이해하는 데에 오래 걸렸다.

오늘 문제를 접한 시점에는

입력을 리스트로 구현한 트리에 중위 표기로 넣고,

후위 순회하여 뽑아내겠다는 생각으로 접근했는데,

내 머리가 아직 그걸 할 수 있는 단계는 아닌 것 같았다.

접근 방식 조차 기억이 안 났던 것이다…

후위 표기식이란 건

일반적으로 사용하는 중위 표기식은 컴퓨터가 읽어들이기 힘들기 때문에,

컴파일 단계에서 stack만으로 간단히 계산할 수 있는 후위 표기식으로 변환한다고 한다.

\[A + B \times C \div D + E\]

컴퓨터는 위의 식을 어떻게 읽을 수 있을까?

처음 등장한 + 에서 A와 B를 더해버리면 B*C 단계에서 문제가 생긴다.

무조건 +가 등장한다고 뒤의 것을 더해선 안 되고, 그 뒤의 부호 까지 확인해야 하는 것이다.

과연 고귀하신 컴퓨터님께서 그런 귀찮은 작업을 해야할까?

위의 중위 표기식을 후위 표기식으로 바꾸면 아래와 같다.

\[A B C \times D \div + E +\]

후위 표기식을 계산하는 방법은 다음과 같다.

1. 식의 앞부터 읽어나가며 수(위의 알파벳)이 나올 경우 Stack에 넣는다.

   stack = [A, B, C] 라고 가정하자.

2. 만약 부호가 등장하면, 스택에서 두 개의 값을 가져온 뒤 해당 부호로 연산하여 다시 값을 넣는다.

   곱연산 기호를 만나 B와 C를 가져와 BC로 만들고 다시 스택에 넣을 경우, stack = [A, BC]

3. 식이 끝날 때까지 1과 2를 반복한다!

   이 경우, 컴퓨터는 당장에 읽은 수와 부호만 처리하면 된다!

스택의 변화를 나열해보자면,

ABC [A, B, C] * [A, BC] D [A, BC, D] / [A, BC/D] + [A+BC/D] E [A+BC/D, E] + [A+BC/D+E]

결과 : A+B*C/D+E

이렇게 변화하여, 마지막에는 중위 표기식으로 돌아오게 되는 것이다!

알파벳 대신 수를 넣어서 계산한다면 정답이 바로 등장한다.

후위 표기로 만들기

문제 조건

A * B가 AB로 표현되는 일은 없으며,

사용되는 기호는 + - / * ( ) 여섯 개가 끝이며,

피연산자는 A ~ Z 까지의 알파벳이다.

사칙연산 네 개만 있다면 코드가 훨씬 짧아지겠지만, 괄호가 있어 따로 처리해줘야 한다.

괄호 안은 바깥의 식과 독립되기 때문에, 회귀로 들어가서 처리할 수도 있을 것이다.

일단은 전역환경에서 후위 표기식 담을 str형 변수 result와 stack 하나만 사용하여 풀어보자.

풀이 과정

1. 피연산자(알파벳, 수)를 만나면 result에 담는다.

2. 연산자를 만나면 종류를 판별한다.

   2-1. 만약 stack이 비어있다면, 종류 불문 일단 넣는다.

3. 괄호의 경우

   3-1. ( 여는 괄호일 경우, 무조건 stack에 넣고 넘어가면 된다.

     이는 새로운 계를 여는 셈이므로, 하나의 기준이 된다.

   3-2. ) 닫는 괄호의 경우, 해당 계를 닫는 상황이므로

     여는 괄호가 나올 때까지 값들을 전부 pop해서 result에 붙여준다.

4. 곱연산, 나눗셈의 경우

   4-1. top 값이 곱연산, 나눗셈인 경우,

     stack을 pop하여 result에 붙여준다.

     top이 곱 또는 나눗셈이어야 하는 이유는 다음과 같다.

     top = +,일 때, 현재 처리하는 기호가 /인데 만약 +를 처리해버리면,

     A+B/C 에서, /보다 +를 먼저 처리하는 것이므로, 연산 순서가 맞지 않는다.

     top = * 로 가정하면, A*B/C 이므로 처리에 문제가 없는 것이다.

     현재 검사 중인 기호의 다음에 올 수 또는 기호를 알 수 없기 때문에

     이미 스택에 들어간 이전 기호에 대해서만 처리를 할 수 있다.

   4-2. 그 다음 현재 처리 중인 기호를 stack에 넣어준다.(append)

   4-3. top이 합차(+,-) 연산인 경우, 위의 설명에 따라 넘어간다.

5. 덧셈, 뺄셈 (합차)의 경우

   5-1. top의 연산자 종류에 불문하고,

     현재 계가 끝날 때까지 stack을 pop하여 result에 붙이는 걸 반복한다.

   5-2.   +, -는 연산 순서의 마지막이기 때문에, 앞에 존재하는 연산을 모두 처리해도 상관 없다.

     A-B/C+D에서, 현재 +를 처리한다고 가정하자.

     result = ABC, stack = [-, /] 이다.

     처리해야 하는 연산은 + 기준 좌변이므로 모두 연산 순서가 +보다 빠르다.   이는 stack의 top이 +, -여도 변함이 없다.

     그렇게 현재 계의 연산을 모두 처리하고, 현재 처리 중인 기호를 넣으면 된다.

6. stack에 남은 연산자를 pop하여 result에 붙인다.

정답 코드

S = sys.stdin.readline()

stack = []
result = ''

for i in S:
    if i.isalpha():
        result += i
    else:
        if not stack:
            stack.append(i)
        elif i == '(':
            stack.append(i)
        elif i == ')':
            while stack and stack[-1] != '(': # 계를 끝낼 때까지
                result += stack.pop()
            stack.pop()
        elif i in '/*':
            while stack and stack[-1] in '/*': # stack top이 곱, 나눗셈인 경우
                result += stack.pop()
            stack.append(i)
        elif i in '+-':
            while stack and stack[-1] != '(': # 현재 계가 끝날 때까지
                result += stack.pop()
            stack.append(i)

while stack:
    result += stack.pop()

print(result)