[백준 1918] 후위 표기식 - Python

문제 보기

[사용한 알고리즘]

스택(stack)

 

[문제 접근]

후위 표기식은 중위 표기식과 달리 괄호가 없는 식이기 때문에 연산자들의 우선순위와 스택을 활용하면 구현하고자 하였습니다.

 

[알고리즘]

1. 중위 표기식을 입력받습니다.

2. 첫 번째 문자부터 순서대로 탐색합니다.

 - 연산자가 아니면 postfix에 더합니다. (postfix -> 최종 식)

 - '(' 연산자는 s에 삽입합니다. (s -> 연산자 저장 스택)

 - ')' 연산자는 '(' 연산자를 만날 때까지 스택에 있는 값들을 pop 한 후 postfix에 더합니다.

 - '+' 혹은 '-' 연산자는 '(' 연산자를 만날 때까지 스택에 있는 값을 pop 한 후 postfix에 더합니다.

 - '*' 혹은 '/' 연산자는 '*' 혹은 '/' 연산자를 만날 때까지 스택에 있는 값을 pop 한 후 postfix에 더합니다.

3. s에 남은 연산자들을 pop 하여 postfix에 더합니다.

 

각각의 stack에서 만나는 조건이 다른 이유는 연산자들의 우선순위가 +, / > +, - > ) 이기 때문입니다.

중위 표기식보다 식을 해석하기에는 어려움이 있지만 괄호를 사용하지도 않고 연산자들의 우선순위를 고려한 식을 만들 수 있다는 것이 신기하였습니다.

 

[코드]

from collections import deque


if __name__ == "__main__":
    infix = list(map(str, input().strip()))

    s = []
    postfix = ""

    for i in range(len(infix)):
        if 'A' <= infix[i] <= 'Z':  # 연산자가 아니면 postfix 에 더합니다.
            postfix += infix[i]
        else:
            if infix[i] == ')':
                while len(s) != 0 and s[-1] != '(':
                    postfix += s.pop()
                s.pop()
            elif infix[i] == '+' or infix[i] == '-':
                while len(s) != 0 and s[-1] != '(':
                    postfix += s.pop()
                s.append(infix[i])
            elif infix[i] == '*' or infix[i] == '/':
                while len(s) != 0 and (s[-1] == '*' or s[-1] == '/'):
                    postfix += s.pop()
                s.append(infix[i])
            elif infix[i] == '(':
                s.append(infix[i])

    while len(s) != 0:
        postfix += s.pop()

    print(postfix)