[BOJ] 1918 후위 표기식 (Python / 파이썬)

🧷 문제

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

주어진 중위 표기식(infix)을 후위 표기식(postfix)로 바꾸는 문제이다. 문제에 나와있다시피 연산자의 우선순위에 따라 스택에서 push, pop의 과정을 통해 해결할 수 있다.

🛠 풀이

이 문제의 중요한 포인트는 연산자의 우선순위를 비교할 때, 우선순위가 같다면 stack안에 들어있는, 즉 식에서 왼쪽에 위치한 연산자를 처리해준다는 것이다.

Step 1.
 expression리스트를 처음부터 한 문자씩 탐색한다.
 expression[i]가 알파벳이라면 res라는 결과 리스트에 append해준다.

Step 2.
 expression[i]가 알파벳이 아니고 연산자라면 우선순위에 맞게 처리를 해준다.
 expression[i]가 (, 여는 괄호라면 일단 stack에 push 해준다.
 *나 /라면 while문을 돌면서 stack이 비어있지 않다면 stack의 top이 우선순위가 같은 *나 /는 먼저 들어왔기 때문에 stack에서 pop 한 후에 res에 append 해준다. 우선순위가 낮은 연산자가 stack의 top 일 경우에는 expression[i]를 stack에 push 해준다.
 +나 -라면 이들보다 낮은 우선순위를 가진 연산자가 없기 때문에 stack이 비어있지 않을 때까지 (이 아닐 때까지 모두 stack에서 pop 한 후에 res에 append 해준다.
 )라면 stack의 top이 (일 때까지 모든 연산자들을 res에 append 해준다.

Step 3.
 만약 식을 다 탐색했는데도 stack이 남아있다면 어짜피 stack은 우선순위(순서)대로 정렬되어 있기 때문에 res.append(stack.pop())해준다.

🖊 나의 코드

import sys

input = sys.stdin.readline

def solution(expression):
    res = []
    stack_operator = []
    for e in expression:
        if e.isalpha():
            res.append(e)

        else:
            if e == '(':
                stack_operator.append(e)

            elif e == '*' or e == '/':
                while stack_operator and (stack_operator[-1] == '*' or stack_operator[-1] == '/'):
                    res.append(stack_operator.pop())
                stack_operator.append(e)

            elif e == '+' or e == '-':
                while stack_operator and stack_operator[-1] != '(':
                    res.append(stack_operator.pop())
                stack_operator.append(e)

            elif e == ')':
                while stack_operator and stack_operator[-1] != '(':
                    res.append(stack_operator.pop())
                stack_operator.pop()

    while stack_operator:
        res.append(stack_operator.pop())

    return res

if __name__ == "__main__":
    exp = list(map(str, input().rstrip()))

    ans = solution(exp)
    for i in ans:
        print(i, end='')