[SWEA] 계산기3

[SWEA] 계산기3

Problem URL : 계산기3

for tc in range(1, 11):

    M = int(input())
    s = list(str(input()))

    stack = []
    exp = []
    isp = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2}
    icp = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 3}

    for i in range(M):
        if s[i].isdigit():
            exp.append(s[i])
        else:
            if s[i] == ')':
                while stack[-1] != '(':
                    exp.append(stack.pop())
                stack.pop()
            else:
                while stack and isp[stack[-1]] >= icp[s[i]]:
                    exp.append(stack.pop())
                stack.append(s[i])

    while stack:
        exp.append(stack.pop())

    for i in range(len(exp)):
        if exp[i].isdigit():
            stack.append(exp[i])
        else:
            b = int(stack.pop())
            a = int(stack.pop())
            if exp[i] == '+':
                stack.append(a + b)
            elif exp[i] == '-':
                stack.append(a - b)
            elif exp[i] == '*':
                stack.append(a * b)
            elif exp[i] == '/':
                stack.append(a / b)

    print('#{} {}'.format(tc, stack[0]))

Comments

isp 는 in-stack priority로 스택 안에 있을 때의 연산자 우선순위이고
icp 는 in-coming priority로 스택에 들어올 때 연산자 우선순위이다.
들어오는 연산자 입장에서 우선순위가 같거나 높은 것들은 먼저 계산되어야 하기에 후위 표현식(exp)에 들어가게 된다.