[Python] 1918: 후위 표기식

 

문제 링크

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

 

 

후위 표기식의 경우 개인적으로 Stack의 정수라고 보기 때문에 이야기를 조금 하고 넘어가겠다.

 

3 + 5 * 7처럼 우리가 실생활에서 사용하는 표기식은 '중위 표기식'이라고 한다.

3 5 7 * + 처럼 숫자가 앞, 수식이 뒤에 있는 표기식은 '후위 표기식'이라고 한다.

 

뭐 어떻게 봐야되는지도 모르겠고, 복잡해보이기만 하는 후위 표기식을 왜 사용하는 것일까?

두뇌풀가동!!!! 출처:SBS/나무위키

 

우리는 인간이기 때문에 5*7을 먼저 해야 한다는 사실을 알고 있다. 하지만 컴퓨터는 선형적으로 데이터를 읽기 때문에 해당 방식을 사용하는 것을 비효율적이다. 우리는 컴퓨터가 더 빠르고 효율적으로 계산을 할 수 있도록 Stack을 이용해서 중위 표기식을 후위 표기식으로 변환할 수 있다!

 

일반적으로 후위 표기식에서 우선 순위는 다음과 같다.

 

우선 순위	연산자
0	괄호()
1	마이너스(-), !
2	곱하기(*), 나누기(/), 나머지(%)
3	더하기(+), 빼기(-)
4	부등호(<, <=, >=, >)
5	등호(==, !=)
6	and(&&)
7	or(||)

 

일단 식에서 문자나 숫자가 들어오면 그대로 출력한다.

만약 수식이 들어온다면, 바로 출력하지 않고 Stack에 push해서 저장해둔다.

이를 반복하다 우선 순위가 높은 수식이 Stack에 들어왔을 때, 해당 수식보다 우선 순위가 낮은 수식을 차례로 Pop하면서 출력한다! (단, 괄호는 출력하지 않는다.)

 

예를 들어보자. A*(B+C)*D를 후위 표기식으로 표기하는 과정은?

 

일단 A를 그대로 출력하고, *는 수식이기 때문에 Stack에 Push한다.

B를 출력하고, (를 Stack에 Push한다. 

(는 *보다 우선순위가 높지만, 그 처리는 )가 나올 때 한다.

C를 출력하고, +를 Stack에 push한다.

그리고 마침내 우선순위 0순위인 )가 나왔기 때문에, (가 나올 때까지 모두 pop한다. 따라서 ABC+가 된다.

그리고 *와 우선순위가 동일한 *가 나오기 때문에, 기존 *는 pop되어 출력되고 새로운 *이 Push된다. D는 그대로 출력된다.

식이 끝났을 때, Stack에 남아있는 수식을 차례롤 pop하여 출력한다.

최종 결과는 ABC+*D*가 된다.

 

여기까지 이해했다면 코드 풀이는 주석만 봐도 이해할 수 있을 것이다.

 

n = list(input())
stack = []

for i in range(len(n)):
    if n[i].isalpha():
        print(n[i], end="")
    else:
        if n[i] == "(":
            stack.append(n[i])
        elif n[i] == ")":
            # 열린 괄호를 만날 때까지 모든 연산자를 출력
            while stack and stack[-1] != "(":
                print(stack.pop(), end="")
            stack.pop()  # 열린 괄호 "(" 제거
        elif n[i] == "*" or n[i] == "/":
            # 스택 최상단이 우선순위 이상이면 출력 후 현재 연산자를 스택에 추가
            while stack and (stack[-1] == "*" or stack[-1] == "/"):
                print(stack.pop(), end="")
            stack.append(n[i])
        elif n[i] == "+" or n[i] == "-":
            # 스택 최상단이 우선순위 이상이면 출력 후 현재 연산자를 스택에 추가
            while stack and (stack[-1] in ["*", "/", "+", "-"]):
                print(stack.pop(), end="")
            stack.append(n[i])
    print(stack)


# 스택에 남은 연산자를 모두 출력
while stack:
    print(stack.pop(), end="")