[BAEKJOON]1918 후위 표기식 - Python

문제 요약

• 알고리즘 분류: Stack
• 난이도: Gold2
• 문제내용:
  • 중위 표기를 후위 표기로 변경해라
• 사이트: https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

문제풀이

   이번에는 문제 유형은 스택 관련 문제이다. 스택에 관란 내용은 여기에서 확인해보면된다.

자료구조 책을 보면 전위표기법, 중위표기법, 후위표기법에서 배운 내용이 있을것이다. 후위 표기법에 대한 내용은 여기에서 공부하고 그 다음 문제 푸는 방법을 보면된다.

후위 표기법에 대한 개념이 잡혀 있으면 그 개념대로 구현을 하면된다.

구현 하기전에 연산자에 대한 우선순위가 있는 낮을수록 우선순위가 높다고 보면된다.

1. () 괄호
2.  *, /
3. +, -

사칙연산의 기본적인 연산우선 순위이다. 

 일단 제일 먼저 할게 결과 담을 변수와 스택 자료 구조를 선언해야 한다. 그 다음 부터 상수나 미지수는 결과에 그대로 저장하고 연산자는 아래와 같이 구현 해주면된다.

-'+', '-' : '(' 만나기 전까지 스택에서 꺼내서 결과에 저장한 다음 현재 연산자를 스택에 저장한다.
-'*', '/' : 스택에서  '*', '-' 제외하고 스택의 맨위에 만났을때 까지 스택에서 꺼내서 결과에 저장한다음 현재 연산자를 저장한다.
-'(' :  스택에 저장한다.
-')' : '(' 만날때 까지 스택에 꺼낸다.

마지막으로 문자나 상수를 결과에 다 저장하면 스택에 남은 연산자들까지 다 꺼내서 결과에 저장한다.

 

정리

• 문자는 결과에 바로 저장한다.
• 연산자는 위와 같은 규칙대로 구현 해준다.
• 문자열 탐색이 끝나면 스택에 남은 연산자는 다 꺼내서 결과에 저장한다.

Code

fomular = input()
stack = []
postfix = []
for f in fomular:
    if f in ('+', '-'):
        while stack and stack[-1] != '(':
            postfix.append(stack.pop())
        stack.append(f)
    elif f in ('*', '/'):
        while stack and stack[-1] in ('*', '/'):
            postfix.append(stack.pop())
        stack.append(f)
    elif f == '(':
        stack.append(f)
    elif f == ')':
        while stack and stack[-1] != '(':
            postfix.append(stack.pop())
        stack.pop()
    else:
        postfix.append(f)

while stack and stack[-1] != '(':
    postfix.append(stack.pop())

print(''.join(postfix))