SWEA 1224. 계산기3(Python)(D4)

후위표기식 3번째 문제이다.
swea 1223, 계산기2에서 소괄호 ()가 추가된 문제다.

연산과정은 아래와 같다(https://glory-summer.tistory.com/86 을 참고했습니다.)

#1.
식: 3+(4+5)*6+7
stack: []
출력(post): 3

#2.
식: 3+(4+5)*6+7
stack: [+]
출력(post): 3
--> stack이 비어있으므로 스택에 +추가

#3.
식: 3+(4+5)*6+7
stack: [+,(]
출력(post): 3
--> (는 +보다 우선순위가 높으므로 스택에 ( 추가

#4.
식: 3+(4+5)*6+7
stack: [+,(]
출력(post): 34

#5.
식: 3+(4+5)*6+7
stack: [+,(,+]
출력(post): 34
--> 스택의 top이 (이므로, 스택에 + 추가

#6.
식: 3+(4+5)*6+7
stack: [+,(,+]
출력(post): 345

#7.
식: 3+(4+5)*6+7
stack: [+,(,+] -> [+,(] -> [+]
출력(post): 345+
--> )가 나오면, stack에서 (가 나올때 까지 계속 출력으로 pop한다.
이때, (와 )은 출력하지 않음

#8.
식: 3+(4+5)*6+7
stack: [+,]
출력(post): 345+
--> 는 +보다 우선순위 높으므로 스택에 추가

#9.
식: 3+(4+5)*6+7
stack: [+,]
출력(post): 345+6

#10.
식: 3+(4+5)*6+7
stack: [+]
출력(post): 345+6+
--> i가 +이므로 stack의 top이 +보다 우선순위가 작거나 같을때 까지 pop하고 마지막으로 i(+) 출력

#11.
식: 3+(4+5)*6+7
stack: [+]
출력(post): 345+6+7

#12.
식: 3+(4+5)*6+7
stack: []
출력(post): 345+6+7+
--> 스택에 남은 연산자 출력

즉, 1223번 문제에서 변한 내용은 i=="(" 인경우, stack에 추가.
i==")인경우, stack의 top이 (가 나올때 까지 pop, 그리고 stack에서 (는 그냥 제거(post에 넣지 않음)

def priority(a):
    if a=='*':
        return 3
    elif a=='+':
        return 2
    else:
        return 1

res=[]
for m in range(10):
    tmp=0
    N=int(input())
    stack=[]
    post=[]
    cal=[]
    S=input()
    for i in S:
        if not stack and (i in "()*+"):
            stack.append(i)
        elif stack and (i in "()*+"):
            if i=="(":
                stack.append(i)
            elif i==")":
                while stack[-1]!="(":
                    post+=stack.pop()
                stack.pop()
            else:
                while stack:
                    if priority(stack[-1])<priority(i):
                        break
                    else:
                        post+=stack.pop()
                stack.append(i)
        else:
            post+=i
    while stack:
        post+=stack.pop()
    
    for i in post:
        if i not in '*+':
            cal.append(int(i))
        elif i=='+':
            cal.append(cal.pop()+cal.pop())
        elif i=='*':
            cal.append(cal.pop()*cal.pop())
    tmp=cal.pop()
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))