[baekjoon] 백준 1918번 : 후위 표기식 (by python 파이썬) 스택 stack

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

1918번: 후위 표기식

 

정답 code

# 후위 표기식
pn = input()
stack = [] 
res = '' #결과값 저장
for p in pn:
    #알파벳일때, 결과값에 추가
    if p.isalpha():
        res += p
    else:
        # ( 일때
        if p =='(':
            stack.append(p)
        # *, / 인경우 같은 우선순위인 *, / 가 있으면 결과값에 추가
        elif p == '*' or p == '/':
            while stack and (stack[-1] == '*' or stack[-1]=='/'):
                res += stack.pop()
            stack.append(p)
        # +, - 인경우 제일 낮은 우선순위임으로 자신보다 높은 연산자 결과값에 추가
        elif p == '+' or p == '-':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.append(p)
        # )일때 스택속에 ()사이의 값 결과값에 저장
        elif p == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()

while stack:
    res += stack.pop()
print(res)

 

solution

스택을 사용하여 해결해야 하는 문제다. 

스택과 결과 값을 저장할 res 선언하여 스택에 저장된 연산자들을 우선순위에 맞춰 결과값에 저장해주면된다.

 

1. 알파벳이면 결과값에 저장

2. ' ( ' 이면 스택에 추가

3. ' * ' , ' / ' 인경우 같은 우선순위인 ' * ', ' / ' 가 스택에 있다면 스택에서 결과값으로 옮긴후 스택에 추가

ex)  A*B/C = AB*C/ 

4. '+', '-'  인경우 자신보다 낮은 우선순위가 없음으로 스택에 자신보다 높은 연산자 추가 '( ' 제외 

ex) A*(B-C) = ABC-*

5. ' )' 인경우 스택속에 ( ) 사이의 값 결과값에 추가 

6. 스택 속의 남은 값 결과값에 저장