BOJ 1918 후위 표기식

https://www.acmicpc.net/problem/1918
시간 2초, 메모리 128MB
input :

• 중위 표기식
• +, -, *, /, (, )

output :

• 후위 표기식으로 바뀐 식을 출력

조건 :

• 중위 표기식을 후위 표기식으로 바꾸는 방법

• 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다.

• a+bc는 (a+(bc))의 식과 같게 된다.

• 그 다음에 안에 있는 괄호의 연산자 를 괄호 밖으로 꺼내게 되면 (a+bc)가 된다.

• 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 된다.

---

무슨 괄호를 직접 만들고 해야 하는 줄 알았다.

연산자의 우선순위에 따라 괄호로 묶는다는 것이 힌트인 것같다.
*, / 의 경우에는 다른 연산자들보다 우선적으로 계산되어야 한다. 그렇기에 다른 연산자들보다 우선순위를 크게 한다.

왜 우선순위를 크게 할까????

• 우린 어차피 이 문자열을 앞에서 부터 읽을 것이다. 그게 트리를 읽는 방식이니까.
  그렇다면, 실제로 괄호를 만들지 않고 어떻게 판별을 할까. 우선 스택을 이용할 거다.
  앞에서 부터 나오는 연산자들을 스택에 집어넣고 꺼낼 것이다.

• 어떤 기준으로?
  알파벳이 들어올 때는 관여를 할 필요가 없다,

    if 'A' <= item <= 'Z':
        ans.append(item)

연산자가 들어오는 경우를 따져야 하는데

현재 : '+'를 가지고 있다 이 때, 이미 temp배열에 '*'나 '/'가 들어있는 경우 이들의 연산이 우선이다. 이 것을 어떻게 확인 하냐.

각 연산자의 우선순위를 비교하는 것이다. 서로 비교를 해서 자기보다 작은 놈이 나올 때 까지 계속 끄집어내는 것이다.
그렇게 해서 임의의 괄호를 만들어주는 것이다.

operator = {"*":2, "/":2, "+":1, "-":1, "(":0}

else:
    while len(temp) > 0 and operator[item] <= operator[temp[-1]]:
        ans.append(temp.pop())
    temp.append(item)

실제로 괄호가 입력되는 경우에는 그냥 '(' 의 우선순위를 가장 작게 해서 괄호보다 우선순위가 작은 게 없어서 다른 연산자들이 나오지 않도록 한다.
이렇게 하면 괄호 안의 연산자들 부터 계산을 할 수 있다.

    elif item == '(':
        temp.append(item)
    elif item == ')':
        while temp[-1] != '(':
            ans.append(temp.pop())
        temp.pop()

import sys

data = sys.stdin.readline().rstrip()
ans = []
temp = []
operator = {"*":2, "/":2, "+":1, "-":1, "(":0}

for item in data:
    if 'A' <= item <= 'Z':
        ans.append(item)
    elif item == '(':
        temp.append(item)
    elif item == ')':
        while temp[-1] != '(':
            ans.append(temp.pop())
        temp.pop()
    else:
        while len(temp) > 0 and operator[item] <= operator[temp[-1]]:
            ans.append(temp.pop())
        temp.append(item)

while temp:
    ans.append(temp.pop())
print("".join(ans))

우선순위를 임의로 만들어 주고, while문을 사용해서 자기보다 우선순위가 작은 놈을 찾는 것이 가장 중요하다.