[알고리즘 문제 풀이][파이썬] 백준 1918번: 후위 표기식

백준 1918 문제 링크: https://www.acmicpc.net/problem/1918

📑 문제 설명

중위 표기법이 주어졌을 때 후위 표기법으로 바꾸어 출력하는 프로그램 작성

입력: 중위 표기식
출력: 후위 표기식

💡 문제 해결 방법

반복문을 사용하여 중위 표기식 문자열 길이만큼 반복한다.
1. 피연산자(A~Z)일 경우, 바로 출력
2. '(' 일 경우, stack에 push
3. 연산자일 경우, 우선순위를 고려
(연산자의 우선순위: *, / > +, -)
: stack top에 있는 연산자가 현재 연산자보다 우선순위가 높거나 같을 경우, stack.pop() 후 push(stack top >= 현재 연산자)

• stack top: + or -, 현재 연산자: * or /
  : stack에 현재 연산자 push
• stack top: + or -, 현재 연산자: + or -
  : stack이 빌 때까지, 현재 연산자 우선순위와 같거나 낮을 동안 출력후 현재 연산자 push
• stack top: or /, 현재 연산자: or /
  : stack이 빌 때까지, 현재 연산자 우선순위와 같거나 낮을 동안 출력후 현재 연산자 push
• stack top: * or /, 현재 연산자: + or -
  : stack이 빌 때까지, 현재 연산자 우선순위와 같거나 낮을 동안 출력후 현재 연산자 push

4. ')'일 경우, '('가 나올 때까지 stack.top 출력

💻 코드

import sys


def postfix(post):
    stack = list()

    for i in range(len(post) - 1):
        if (post[i] == "("):
            stack.append(post[i])
        elif (post[i] == "+" or post[i] == "-"):
            while(stack and stack[-1]!='('):
                print(stack.pop(), end="")
            stack.append(post[i])
        elif (post[i] == "*" or post[i] == "/"):
            while (stack and stack[-1] != '(' and (stack[-1] == "*" or stack[-1] =='/')):
                print(stack.pop(), end="")
            stack.append(post[i])
        elif (post[i] == ")"):
            while (stack and stack[-1] != '('):
                print(stack.pop(), end="")
            stack.pop()
        elif (post[i] >= 'A' and post[i] <= 'Z'):
            print(post[i], end="")

    if (len(stack) >0):
        for i in range(len(stack)):
            print(stack.pop(), end="")


if __name__ == '__main__':
    post = sys.stdin.readline()
    postfix(post)

💟 추가적으로 알게 된 점