[BOJ 1918] 후위 표기식

후위 표기식(BOJ 1918번)

📕 문제

[문제 링크]

✏️ 아이디어 스케치

"후위 표기식이라는 제목을 보자마자 이 문제는 스택을 사용하는 문제이다."라고 바로 떠올렸다. 하지만 스택을 사용해서 어떻게 풀어야 할지는 쉽게 떠오르지 않았다.

풀이방법을 고민하고 고민하다가 결국 방법을 떠올리지 못해 결국 구글링을 통해서 후위 표기식 변환방법을 참고하여 풀이하였다. 스택 문제의 기본적인 형태라고 생각했는데 막상 풀려고 하지 쉽게 풀지 못해서 당황스러웠다.

이후에 다시 까먹지 않고 혹시나 까먹어도 다시 참고하기 위해 후위 표기식 변환방법에 대해 아래에 정리했다.

📃 소스 코드

# 1918 - 후위 표기식
expression = input()

expression = list(expression)
op_stack = []
priority = {'+': 1, '-': 1, '*': 2, '/': 2}

for e in expression:
    if e not in priority and e not in ['(', ')']:
        print(e, end='')
    else:
        if not op_stack:
            op_stack.append(e)
        else:
            if e == ')':
                while op_stack[-1] != '(':
                    print(op_stack.pop(), end='')
                op_stack.pop()
            else:
                while op_stack and e != '(' and op_stack[-1] != '(' and \
                        priority[op_stack[-1]] >= priority[e]:
                    print(op_stack.pop(), end='')
                else:
                    op_stack.append(e)
while op_stack:
    print(op_stack.pop(), end='')

💡 필요 개념

후위 표기식 변환 방법

1. 피연산자는 그대로 출력한다
2. 연산자일 경우
    2-1. 스택이 비어있으면 스택에 추가한다.
    2-2. 스택이 비어있지 않으면 스택의 top이 자신보다 낮은 우선순위의 연산자일 때까지 pop한 후 자신을 스택에 추가한다.
3. 여는 괄호일 경우 스택에 바로 추가한다.
4. 닫는 괄호일 경우 여는 괄호가 나올 때까지 stack을 pop한다.
5. 문장이 끝나면 스택에 남아있는 연산자를 모두 pop한다.

A+B*C-D/(E+F) 의 후위 표기식

A+B*C-D/(E+F)

A는 피연산자이므로 그대로 출력한다.

출력 : A

A+B*C-D/(E+F)

스택이 비어있으므로 연산자 +를 추가한다.

+

A+B*C-D/(E+F)

B는 피연산자이므로 그대로 출력한다.

출력 : AB

A+B*C-D/(E+F)

* 보다 스택의 top인 + 가 우선순위가 낮으므로 스택에 추가해준다.

+	*

A+B*C-D/(E+F)

C는 피연산자이므로 그대로 출력한다.

출력 : ABC

A+B*C-D/(E+F)

- 보다 스택의 top인 * 가 우선순위가 높으므로 스택에서 pop한다.

+

출력 : ABC*

pop한 이후의 스택의 top인 + 도 - 와 우선순위가 같으므로 pop한다.
이 때, 스택은 빈 상태가 된다.

출력 : ABC*+

이 후, 스택이 비어있으므로 - 를 스택에 추가한다.

-

A+B*C-D/(E+F)

D는 피연산자이므로 그대로 출력한다.

출력 : ABC*+D

A+B*C-D/(E+F)

/보다 스택의 top인 - 가 우선순위가 낮으므로 스택에 추가해준다.

-	/

A+B*C-D/(E+F)

여는괄호 ( 는 스택에 항상 추가한다.

-	/	(

A+B*C-D/(E+F)

E는 피연산자이므로 그대로 출력한다.

출력 : ABC*+DE

A+B*C-D/(E+F)

스택의 top이 ( 이므로 + 를 스택에 추가한다.

-	/	(	+

A+B*C-D/(E+F)

F는 피연산자이므로 그대로 출력한다.

출력 : ABC*+DEF

A+B*C-D/(E+F)

스택의 top에서부터 ( 까지의 모든 연산자를 pop한다.

-	/

출력 : ABC*+DEF+

A+B*C-D/(E+F) 수식 탐색 종료

수식을 모두 순회한 이후 스택의 모든 연산자를 pop한다.

최종 출력 : ABC*+DEF+/-