백준 1918 후위 표기식

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

1918번: 후위 표기식

전형적인 스택 활용 문제이다.

스택을 사용할 수 있는 문제/경우들에는 항상 어떠한 순서나 우선순위와 같은 개념이 묻어있다. 스택이 비어있다면 스택에 값을 담고, 값이 있다면 우선순위를 체크하여 어떤 걸 처리할지 정한다. 

이 문제처럼 괄호없이도 연산 순서를 표현하는 후위 표기식 표현이나 증가/감소 수열 구하기 등등 반드시 경험해야할 문제중의 하나라고 생각한다. 스택을 활용하게 되면 보통 O(N)의 풀이가 가능하게 되는 경우가 많다. 나중에 처리할 부분이 스택에 담기고 앞으로 전진하다가 때가 되었을 때 뽑아내기 때문에 인풋 길이만큼의 시간복잡도를 갖게 되는 경우가 많고 이는 사실상 가장 최고 효율이 아닐까라고 생각한다. 일단 입력으로 들어오는 모든 값을 한번은 봐야하니깐.

 

어쨌든 스택은 참 중요한 자료구조라고 생각하며,

이 문제에서 스택이 어떻게 쓰일 수 있는지에 대해 관찰하였다.

 

<관찰>

처음 이 문제를 봤을 때, 문자들 처리에 대한 고민도 많이 했다. 괄호가 있으니 괄호 안에 있는 문자들이 바깥에 있는 것들에 비해 우선순위를 갖는다고 생각했기 때문이다. 하지만 연산자를 기준으로 앞뒤 문자를 같이 묶어서 처리하기에 문자들(피연산자)은 크게 고민없이 출력할 수 있다. 사실 이것을 깨닫는 것부터 쉽지 않다.

 

이제 문제는 연산자인데, 연산자들은 다음의 경우들에 한해 출력될 수 있다.

1. 괄호가 닫힐 때. 이 때 해당 괄호안에 포함되어 있었던 연산자들이 모두 출력된다.
2. 같은 괄호 내에서 (혹은 괄호가 없는 바깥) 새로운 연산자가 왔을 때 기존 연산자와 비교 후 우선순위가 높으면 출력된다.
3. 주어진 수식을 모두 읽었을 때. 그 동안 쌓아온 연산자들을 모두 출력한다.

<해결>

위의 경우들을 표현하기 위해서 어떤 단계/뎁스(depth, 변수명 d를 사용)의 괄호인지 기록할 필요가 있다. 필자의 경우, 처음에 d=0으로 시작해서 괄호가 생길때마다 그 값을 증가시켜주었다. 그래서 스택에 저장할 때 연산자와 그 d값을 같이 넣어두면, 어떤 연산자가 어떤 괄호 안 연산자인지를 확인할 수 있다. 

 

<주요 내용>

스택

 

<코드>

Python

파이썬의 리스트는 (list()) 자제적으로 스택 기능을 갖고 있다. 그것을 활용하였다.

import sys
si = sys.stdin.readline

s, op, d = si()[:-1], [], 0
order, p = {'+': 0, '-': 0, '*': 1, '/': 1, }, {'(', ')'}

for e in s:
    if e in p:
        if e == '(':d += 1
        
        # 본문 1번 케이스: 괄호 닫힐 때
        else:
            while op and op[-1][0] == d:print(op.pop()[1],end='')
            d -= 1
    elif e not in order:print(e,end='')
    else:
        if not op or op[-1][0] < d:op.append([d, e])
        elif order[op[-1][1]]<order[e]:op.append([d, e])
        
        # 본문 2번 케이스: 동일 괄호 또는 동일 d내에서 연산자 우선순위 비교
        else:
            while op and op[-1][0]==d and order[op[-1][1]]>=order[e]:
                print(op.pop()[1],end='')
            op.append([d, e])

# 본문 3번 케이스: 입력을 모두 읽었을 때:
while op and op[-1][0] == d:print(op.pop()[1],end='')