[SWEA] 1224. 계산기3 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14tDX6AFgCFAYD 

SW Expert Academy

< 📝 문제 >

문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오.

예를 들어

“3+(4+5)*6+7”

라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다.

"345+6*+7+"

변환된 식을 계산하면 64를 얻을 수 있다.

문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 문자열 중간에 괄호가 들어갈 수 있다.

이때 괄호의 유효성 여부는 항상 옳은 경우만 주어진다.

피연산자인 숫자는 0 ~ 9의 정수만 주어진다.

< ❓ 생각 >

1223. 계산기 2에서 괄호가 추가된 상황

https://chaemi720.tistory.com/47

[SWEA] 1223. 계산기2 - Python

 

중위 표현식에서 '('를 먼저 확인하므로 처음에는 우선순위가 높음

'('가 stack에 들어가는 순간 그 괄호 안의 계산식에서 순서 확인해야 하니 '('가 가장 마지막이므로 '('의 우선순위가 가장 낮아짐

!!! 우선순위가 바뀐다는 것을 생각!!

 

< 💻 코드 >

# 테스트 케이스 개수
T = 10
for tc in range(1,T+1):
    # 테스트 케이스의 길이
    N = int(input())
    # 테스트 케이스
    TC = list(input())

    # in-stack priority
    isp = {'*':2, '+':1, '(':0}
    # in-coming priority
    icp = {'*':2, '+':1, '(':3}

    # 1. 후위 표기식으로 바꾸기
    result_ls = []
    stack = []
    for i in TC:
        # 숫자면 결과에 넣기
        if i in '0123456789':
            result_ls.append(i)
        # '*' or '+' or '('
        elif i in '*+(':
            # 스택이 비어있으면
            if not stack:
                stack.append(i)
            # 스택이 비어있지 않으면
            else:
                # stack[-1] 보다 우선순위가 낮다면 stack에 있는 연산자 다 빼내기
                if isp[stack[-1]] >= icp[i]:
                    while stack and isp[stack[-1]] >= icp[i]:
                        result_ls.append(stack.pop())
                stack.append(i)
        # ')'
        else:
            while stack[-1] != '(':
                result_ls.append(stack.pop())
            stack.pop()
    # 남아있는 연산자 모두 넣기
    while stack:
        result_ls.append(stack.pop())

    # 2. 계산하기
    result = []
    i = 0
    for i in result_ls:
        if i != '*' and i != '+':
            result.append(i)
        elif i == '+':
            result[-2] = int(result[-2]) + int(result[-1])
            result.pop()
        else:
            result[-2] = int(result[-2]) * int(result[-1])
            result.pop()

    print(f'#{tc} {result[0]}')

< ❗ 느낀 점 >

괄호를 생각하는 것이 연산자만 있을때보다 조금 어려웠다