[백준] 1918 후위 표기식, python

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

 

 

결과를 저장할 스택, 연산자를 저장할 스택을 2개가 필요하다.

 

만약 피연산자라면 바로 결과 스택에 넣는다.

여는 괄호라면 연산자 스택에 넣는다.

스택이 비어있거나 스택의 최상단이 여는 괄호라면 연산자를 연산자 스택을 넣는다.

스택 최상단의 연산자가 넣으려는 연산자의 우선순위보다 높거나 같으면 연산자 스택에서 꺼낸다.

예를 들어 현재 스택최상단이 *고 넣으려는 연산자가 +라면 *를 꺼내야 한다.

 

아래는 A * (B+C)를 변환하는 과정이다.

수식 인덱스	결과 스택	연산자 스택	설명
A	[A]	[]	피연산자는 바로 결과스택에 넣는다.
*	[A]	[*]	연산자 스택이 비었으므로 넣는다.
(	[A]	[*(]	여는 괄호는 바로 연산자 스택에 넣는다.
B	[AB]	[*(]	피연산자는 바로 결과스택에 넣는다.
+	[AB]	[*(+]	스택 최상단이 여는 괄호이므로 연산자 스택에 넣는다.
C	[ABC]	[*(+]	피연산자는 바로 결과스택에 넣는다.
)	[ABC+]	[*]	닫는 괄호가 나오면 여는괄호가 나올때까지 연산자 스택에서 빼서 결과 스택에 넣는다.
	[ABC+]	[]	마지막으로 연산자 스택에 남은걸 전부 꺼내어 결과 스택에 넣는다.

 

 

str = input()

def solve(str):
    result = []
    stack = []

    def level(op):
        return 2 if op in '*/' else 1

    for x in str:
        # 피연산자는 바로 결과 스택에 넣음
        if 'A'<=x and x<='Z':
            result.append(x)
        # 여는 괄호라면 연산스택에 넣음
        elif x=="(":
            stack.append(x)
        # 닫는 괄호면 여는 괄호가 나올때가지 스택에서 꺼냄
        elif x==")":
            while stack and stack[-1]!="(":
                result.append(stack.pop())
            stack.pop()
        # 연산자라면 스택에서 상위연산자가 있으면 꺼냄
        elif x in '/*-+':
            while stack and stack[-1]!="(" and (level(stack[-1])>=level(x)):
                result.append(stack.pop())
            stack.append(x)

    # 남은 연산자를 다 꺼냄
    while stack:
        result.append(stack.pop())

    return ''.join(result)

print(solve(str))