백준: 1918 후위 표기식

문제

1918번: 후위 표기식

 

문제 풀이

 stack을 활용하고, 연산식에 대한 특성을 잘 이해하면 쉽게 문제를 풀 수 있다. 피연산자와 연산자에 따라, stack에 push 할지가 결정되며 연산자의 우선순위와 괄호를 고려하여 처리하면 된다.

 

• 피연산자가 입력되면 stack에 push하지 않고 출력한다. 
• 연산자는 stack에 push 한다.
• stack에 push 하고자 하는 연산자가 닫는 괄호 ' ) '라면 여는 괄호 ' ( '를 만날때 까지 stack에서 pop하여 출력한다.
• stack top의 연산자가 현재 입력된 연산자 보다 우선순위가 높다면, 우선 순위를 위해 우선적으로 출력한다.

 즉, 연산자는 stack에 피연산자는 출력을 하면서, stack에 처리할 연산자들의 우선순위와 괄호를 고려하여야 한다.

 

코드

from sys import stdin

pri = {
    '*': 2,
    '/': 2,
    '+': 1,
    '-': 1,
    '(': 0
}

if __name__ == "__main__":
    math_expr = stdin.readline()[:-1]
    stack = []
    answer = ''
    for c in '(' + math_expr + ')':
        if c.isalpha():
            answer += c
        elif c == '(':
            stack.append(c)
        elif c == ')':
            while True:
                op = stack.pop()
                if op == '(':
                    break
                answer += op
        else:
            while stack and pri[c] <= pri[stack[-1]]:
                answer += stack.pop()
            stack.append(c)

    print(answer)