SWEA 1223. 계산기2(Python)(D4)

swea 1222, 계산기1 문제에서 *연산이 추가되었다.
연산에 우선순위가 들어간다.
먼저 중위 -> 후위표기식으로 바꿔준다

• 숫자일 경우 바로 post로 출력
• +,*일경우 스택이 비어있을 경우 i를 바로 push
• 스택이 비어있지 않을경우, i와 stack의 top을 비교한다
  - i가 stack의 top보다 우선순위가 높을때 까지 아래방법을 반복한다
  • top이 i보다 우선순위가 낮거나 같으면 stack에서 pop해 post에 출력
• i가 top보다 우선순위가 높으면 빠져나와 stack에 i를 push

후위표기식의 계산은 동일하다.

• post의 i번째가 숫자인 경우, cal에 push
• post의 i번째가 *,+인경우, cal에 저장된 2개의 숫자를 pop해 연산해서 다시 push
• 마지막 cal에 저장된 숫자를 pop하면 결과!

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=='+' or i=='*'):
            stack.append(i)
        elif stack and (i=='+' or i=='*'):
            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]))