[알고리즘 문제 풀이][파이썬] 백준 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
- ')'일 경우, '('가 나올 때까지 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)
💟 추가적으로 알게 된 점
Author And Source
이 문제에 관하여([알고리즘 문제 풀이][파이썬] 백준 1918번: 후위 표기식), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yeomja99/알고리즘-문제-풀이파이썬-백준-1918번-후위-표기식저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)