[백준] 1918 - 후위 표기식

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

1918번: 후위 표기식

문자열처리 문제처럼 보였지만, 의외로 자료구조 문제였다.

아이디어를 구상하고 구체화, 테스트하는데 30분, 코드로 구현하는데 30분 정도 걸린 것 같다.

문제를 이해하는데 큰 어려움은 없었다.

---

풀이 아이디어

---

이 문제를 푸는데 중요한 것은 아래 2가지를 떠올리는 것이다.

1. '우선 순위가 높은 연산자를 먼저 처리한다'

2. 괄호 내부의 연산은 괄호 외부와 문제 풀이 구조가 동일하다 = 재귀로 접근할 수 있다.

 

이제 이 1번과 2번을 따로따로 구현하면 이 문제를 풀 수 있다.

나는 이걸 구현하는데 머리를 좀 열심히 굴렸던 것 같다.

 

그 결과 내가 떠올린 아이디어는 덱을 사용하는 것이었다.

그 이유는, 덱을 이용하면 덱으로 큐와 스택을 모두 구현할 수 있는데,

이 문제를 풀기 위해서는 스택과 큐를 모두 사용할 필요성이 있었기 때문이다.

---

우선 괄호를 생각하지 않고, 사칙연산만을 생각해보자.

 

1. 덧셈과 뺄셈이 나와도 언제 곱셈, 나눗셈이 나올지 모른다.

따라서 곱셈과 나눗셈이 나올 때까지 모든 피연산자와 연산자를 저장하되, 곱셈과 나눗셈은 즉시 계산한다.

 

이때 사용하는 자료구조는 '스택' 이다.

일단 다 저장하다가 곱셈이나 나눗셈이 나오면 가장 최근의 데이터로 즉시 연산을 진행해야 하기 때문이다.

이때 아무 생각없이 바로 가장 최근 데이터를 꺼내쓰는 것은, 괄호를 생각하지 않고 사칙연산만 생각할 경우

연산자의 좌우에는 반드시 피연산자가 있기 때문이다.

 

이렇게 연산한 데이터는, 그 연산 결과를 묶어서 다시 스택에 저장한다.

그리고 다시 입력데이터를 돌면서 위 과정을 반복한다.

그 결과 전체 수식에 대해서 곱셈, 나눗셈을 1차적으로 처리한 결과물이 스택에 담겨있게 된다.

이 수식에는 사칙연산만 담겨 있으므로, 이제 전체 수식에는 덧셈과 뺄셈만이 남아 있다.

따라서

 

2. 남은 덧셈과 뺄셈은 그냥 앞에서부터 차례대로 계산하면 된다.

이때 사용하는 자료구조는 '큐' 이다.

이를 위해 남은 자료를 앞에서부터 하나씩 꺼내서 후위연산식을 써나가면 된다.

피연산자를 꺼내서, 기존 후위연산식에 피연산자를 붙이고나서 연산자를 붙이는 식으로 쓰면 된다.

 

3. 괄호 내부의 구조는 위 1, 2번이 반복되는 구조이므로, 1과 2를 처리하는 함수를 작성하여

괄호를 만나면 작성한 함수를 재귀적으로 호출한다.

 

이때 함수는 '처리를 시작할 문자열 인덱스'를 인자로 받아서

'처리한 후위 연산식 문자열'을 결과로 반환하도록 짠다.

---

구체적인 구현 예시

---

A*(B+C) 라는 문자열을 처리하는 경우

이 문자열을 전역변수로 따로 저장해두고

인덱스 0부터 이 문자열을 처리하기 위해 함수를 호출한다.

F(0)

 

우선 *, /을 제외한 문자를 스택(실제로는 덱)에 담으면서 곱셈, 나눗셈부터 처리한다.

나는 곱셈, 나눗셈을 처리하기 위해, process 변수를 사용했다.

만약 피연산자를 만났는데, process 변수가 True라면 해당 피연산자를 두번째 피연산자,

스택에 가장 최근에 담았던 피연산자를 첫번째 피연산자,

별도로 저장한 연산자를 연산자로 하여

 

1. A를 만난다. (인덱스 0)

process 변수가 False이므로 스택에 A를 저장한다.

 

2. * 을 만난다. (인덱스 1)

process 변수를 True로 바꾸고, 연산자로 *를 별도 저장한다.

 

3. ( 를 만난다. (인덱스 2)

재귀적으로 함수를 호출한다. 이때 괄호는 빼야하므로

다음 인덱스부터 처리한다.

F(3) 호출

 

4. B+C를 모두 스택(덱)에 저장한다.

(곱셈/나눗셈이 없으므로)

 

5. 이제 덱에서 앞에서부터 하나씩 빼서 B+C를 후위연산식으로 바꾼다.

return "BC+"

 

6. process 변수가 True이므로 리턴받은 값을 두번째 연산자로,

A를 첫번째 연산자로 하여 * 연산을 진행하여 덱에 넣는다.

 

F(3)의 호출로 처리가 완료된 인덱스 이후부터 다시 곱셈에 대한 처리를 진행한다.

(처리할 내용이 없으므로 아무 작업 없이 다음 단계로 이동)

 

7. +,- 연산자가 없으므로 이 과정은 무시된다.

 

8. 최종적으로 처리된 내용을 출력한다.

return "BC+A*

---

실제 코드

---

from collections import deque
import sys


def Process(index):
    d = deque()

    # process *, /
    process = False
    while index < len(s):
        c = s[index]
        if c == '*' or c == '/':
            process = True
            op = c
        elif c == '(': # 여는 괄호가 나오면, 괄호 내용은 따로 처리 후, 처리한 이후 내용부터 다시 처리
            processed, index = Process(index + 1)
            if process:
                op1 = d.pop()
                op2 = processed
                d.append(op1+op2+op)
                process = False
            else:
                d.append(processed)
        elif c == ')':
            break
        else:
            if process:
                # 만약 연산자가 아닌 문자가 나왔는데, process가 True이면, 직전에 *, /가 나온 것이다.
                # 즉 현재 문자가 두번째 피연산자, 덱의 멘 오른쪽 유닛이 첫 번째 피연산자가 된다.
                op1 = d.pop()
                op2 = c
                d.append(op1+op2+op)
                process = False
            else:
                d.append(c)
        index += 1

    # process +, -
    value = d.popleft()
    op = ""
    while d:
        check = d.popleft()
        if check == '+' or check == '-':
            op = check
        else:
            value = value + check + op

    return value, index


s = input()
answer, i = Process(0)
print(answer)