[백준/Python] 1918번 : 후위 표기식

문제

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

---

풀이

중위표기식에서 후위표기식으로 변환하는 것은 스택을 활용하여 풀 수 있다.
후위표기식의 방식에 따라, 계산할 문자를 먼저 문자열에 두고 기호는 스택에 넣어두었다가 출력하면 된다.
하지만, 연산자의 우선순위에 의해 추가적으로 고려해주어야 한다.
우선순위가 더 낮은 연산자가 나오면 더 높은 연산자를 먼저 처리해준다.
또한, 괄호가 나오는 경우 괄호가 닫히는 순간에 괄호가 시작되었던 부분까지 고려하여 변환하면 된다.

---

코드

formula = input()

precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
postfix = ''

for c in formula:
    if c.isalpha():
        postfix += c
    elif c == '(':
        stack.append(c)
    elif c == ')':
        while stack and stack[-1] != '(':
            postfix += stack.pop()
        stack.pop()
    else:
        while stack and stack[-1] != '(' and precedence[c] <= precedence[stack[-1]]:
            postfix += stack.pop()
        stack.append(c)

while stack:
    postfix += stack.pop()

print(postfix)