백준 1918 후위 표기식

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1918

이 문제는 전위 표기식으로 들어온 식을 후위 표기식으로 변경하여 출력하는 문제이다.

풀이

난이도 : GOLD II

처음 문제를 보았을 때 스택을 사용하여 연산자를 관리해주어야겠다고 생각했고, python에 list는 기본적으로 스택의 역할을 할 수 있기 때문에 큰 어려움 없이 문제를 풀 수 있었다.

👉 풀이과정

1) 연산자 우선순위를 나타낼 함수 작성
2) 전위 표기식으로 되어 있는 식을 앞에서부터 한 문자씩 읽기
3) 문자를 읽으면서 연산자가 아닐 경우에는 바로 결과에 추가
4) 연산자일 경우
	(1) 스택이 비어있을 경우 : 스택에 연산자를 추가하고 넘어가기
    (2) 스택에 값이 있을 경우 : 스택 top에 있는 연산자와 현재 연산자의 우선순위를 비교
    	- 스택에 있는 연산자가 우선순위가 더 높을 경우 
        	-> 현재 연산자를 스택에 추가하고 넘어가기
        - 스택에 있는 연산자가 우선순위가 더 낮을 경우
        	-> 스택 top에 있는 연산자가 "("이면 스택에 현재 연산자 추가
            -> 아닐 경우, 스택 top 연산자의 우선순위가 현재 연산자 우선순위보다 커지거나 스택 top 연산자가 "("가 나올 때까지 스택에 있는 값들을 pop해서 결과에 반영, 이후 스택에 현재 연산자를 추가
	(3) 연산자가 ")" 일 경우 : 스택 top에 "("가 나올 때까지 스택에서 값을 빼서 결과에 반영
    
    

문제를 풀 때, 스택을 사용하는 방법을 생각해내면 괄호의 기능을 처리하여야 한다.
구현하면서 예외처리할 때 도움이 되었던 반례는 아래와 같다.

input : G*(A-B*(C/D+E)/F)
answer : GABCD/E+*F/-*


    

코드

# 연산자 우선순위 계산 (연산자가 아닐시 -1)
def get_op(x):
    if x == "(":
        return 0
    if x == "*" or x == "/":
        return 1
    if x == "+" or x == "-":
        return 2
    if x == ")":
        return 3
    
    return -1

cal = str(input())
stack = []

result = ""
for c in cal:
    op = get_op(c)

    # 문자열일 경우 결과에 추가
    if op == -1:
        result += c
        continue

    # 스택이 비어있을 경우 스택에 연산자 추가
    if len(stack) == 0:
        stack.append(c)
        continue

    # ")" 일 경우 "("가 나올 때 까지 스택에서 값을 빼서 출력
    if get_op(c) == 3:
        while stack:
            x = stack.pop()
            if get_op(x) == 0:
                break
            result += x
        continue

    # 연산자 우선순위 반영하여 스택에서 연산자 pop하여 반영
    if get_op(stack[-1]) > get_op(c):
        stack.append(c)
    else:
        if get_op(stack[-1]) == 0:
            stack.append(c)
        else:
            while stack:
                if get_op(stack[-1]) == 0 or get_op(stack[-1]) > op:
                    break
                result += stack.pop()
            stack.append(c)

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