[구현] 백준 1918번 : 후위 표기식 / 골드 3

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

1918번: 후위 표기식

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의

www.acmicpc.net

string = [x for x in input()]
opers = []

dct = {}
dct['*'] = 1
dct['/'] = 1
dct['+'] = 2
dct['-'] = 2

result = ''
count = 0
while string:
    elem = string.pop(0)
    if elem.isalpha():
        result += elem
    else:
        if not opers:
            if elem == '(':
                count += 1
            opers.append(elem)
        else:
            if elem == '(':
                count += 1
                opers.append(elem)

            elif elem == ')':
                while opers[-1] != '(':
                    result += opers.pop()
                opers.pop()
                count -= 1
            else:
                while opers:
                    if opers[-1] == '(':
                        break
                    if dct[opers[-1]] <= dct[elem]:
                        result += opers.pop()
                    else:
                        break
                opers.append(elem)
while opers:
    result += opers.pop()
print(result)

중위 표기식을 후위 표기식으로 바꾸는 법을 여기서 떠올려서 풀기란 매우 쉽지 않다.

바꾸는 원칙 같은 건 인터넷을 참고하고 구현에 초점을 맞춰서 문제를 풀어보는 것이 맞는 듯하다.