[백준 1918] 후위 표기식- python (solved.ac - 골드 2)

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

1918번: 후위 표기식

풀이

문제를 보았을때 알수있는 힌트

후위 표기식을 생각하면서 조건을 어떻게 짜야하는지 고민하며 문제를 풀면 쉽게 풀 수 있다.

1. 알파벳과 표기식이 나오는 경우를 나눈다.

 - 알파벳이 나오는 경우 결과 리스트에 추가한다.

 - 표기식이 나오는 경우 아래에 조건을 따른다.

2. 표기식이 나온경우 조건식

 -  시작하는 괄호가 나오는 경우 : 스택에 쌓아준다.

 - "+"나"-" 가 나오는 경우 :  스택에 쌓인 값을 꺼내준다. 단 시작하는 괄호가 나오면 거기서 멈춘다. 이후 현재 나온  "+"나"-" 을 스택에 쌓는다.

 - "*"나"/"가 나오는 경우 : 스택에 쌓인 값을 꺼내준다. 단, "*" 나 "/" 인 경우에만 꺼내준다.

 - 닫는 괄호가 나오는 경우 : 시작하는 괄호까지 스택을 꺼내주고 시작하는 괄호또 꺼내준다.

3. 스택이 남은 경우 결과 리스트에 스택을 쌓아 준다.

이 조건을 만족하게 코드를 짜면 틀리지 않고 맞을 것이다.

 

import sys

input = sys.stdin.readline

n = list(input().strip())
n_list =["+","-","*","/","(",")"]
stack=[]
result =[]
while n:
    v=n.pop(0)
    if v in n_list:
        # 여기서 조건을 걸어야함.
        if v=="(":
            stack.append(v)
        elif v=="+" or v=="-":
            while len(stack)!=0 and stack[-1]!="(":
                result.append(stack.pop(-1))
            stack.append(v)
        elif v=="*" or v=="/":
            while len(stack)!=0 and (stack[-1] == '*' or stack[-1] =='/'):
                result.append(stack.pop(-1))
            stack.append(v)
        elif v==")":
            while len(stack)!=0 and stack[-1]!="(":
                result.append(stack.pop(-1))
            stack.pop(-1)
    else:
        result.append(v)
while stack:
    result.append(stack.pop(-1))

print("".join(result))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1918.py