계산기3 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1224

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14tDX6AFgCFAYD&categoryId=AV14tDX6AFgCFAYD&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오. 예를 들어 “3+(4+5)*6+7” 라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다. "345+6*+7+" 변환된 식을 계산하면 64를 얻을 수 있다. 문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 문자열 중간에 괄호가 들어갈 수 있다. 이 때 괄호의 유효성 여부는 항상 옳은 경우만 주어진다. 피연산자인 숫자는 0 ~ 9의 정수만 주어진다.

 

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 길이가 주어진다. 그 다음 줄에 바로 테스트 케이스가 주어진다. 총 10개의 테스트 케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 답을 출력한다.

예시

입력	출력
113 (9+(5*2+1)+(3*3*7*6*9*1*7+1+8*6+6*1*1*5*2)*4*7+4*3*8*2*6+(7*8*4*5)+3+7+(2+6+5+1+7+6+7*3*(6+2)+6+6)*2+4+2*2+4*9*3) 85 (4+8+4*(8*5*(7*(6*8)+3+(6+(3+7+1*7*5*4)*3)*2*3+5)+6+7*7)*4+2+9*4+7+2*3*(7*6*1*8)+9+9) ...	#1 672676 #2 1974171 ...

---

2. 문제풀이

들어오는 입력값을 확인하며 후위연산으로 바꿔준다. 후위연산으로 만들기 위해서 숫자를 저장하는 스택과 연산자를 저장하는 스택을 운영한다. 숫자가 나온다면 숫자스택에 넣어주고 연산자가 나온다면 연산자스택의 이전값의 우선순의를 보고 판단하여 계산한다. 후위연산을 위한 분리와 계산이 끝났다면 남은 연산자를 하나의 스택으로 합쳐준다. 이제 하나의 스택의 데이터를 꺼내며 후위연산을 마무리한다. 스택에 남아있는 값이 리턴할 결과값이 된다.

---

3. 소스코드

#D4 1224 계산기 3
 
operator = {'(' : 4, ')' : 4, '*' : 2, '/' : 2, '+' : 3, '-' : 3}
 
def cal(t1, t, t2):
    t1 = int(t1)
    t2 = int(t2)
    if t == '+': return t1 + t2
    elif t == '-': return t1 - t2
    elif t == '*':  return t1 * t2
    elif t == '/':  return t1 // t2
 
T = 10
for a in range(1, T+1):
    input()
    t_input = list(input())
    stack_operater = []
    stack_result = []
 
    for t in t_input:
        #숫자면 넣는다.
        if '0' <= t <= '9':
            stack_result.append(t)
        #여는 괄호거나 스택이 비어있거나 스탭탑이 여는 괄호라면 연산자 집어넣기
        elif t == '(' or not len(stack_operater) or stack_operater[-1] == '(':
            stack_operater.append(t)
        #들어온 연산자가 스택의 연산자보다 우선순위가 높다면 추가하기(낮은 수가 높은 우선순위)
        elif operator[t] < operator[stack_operater[-1]] and t != ')':
            stack_operater.append(t)
        else:
            #위의 내용에 해당하지 않는다면
            #스택이 비지않거나 들어온 연산자가 스택의 탑보다 크거나 같을때까지 반복한다.
            while len(stack_operater) and operator[t] >= operator[stack_operater[-1]]:
                #닫는 괄호라면 괄호없애고 정지한다.
                if stack_operater[-1] == '(':
                    stack_operater.pop()
                    break
                #위의 조건에 해당하지 않는다면 결과 스택에 추가한다.
                stack_result.append(stack_operater.pop())
            #반복이 끝난후 닫는괄호가 아닐때만 연산자스택에 추가하기
            if t != ')':
                stack_operater.append(t)
 
    #남은 연산자를 처리한다.
    while len(stack_operater):
        #스택이 빌때까지 결과스택에 넣어준다.
        temp = stack_operater.pop()
        if temp != '(':
            stack_result.append(temp)
 
    #후위연산 스택을 순회하면서 확인
    for t in stack_result:
        #숫자라면 임시저장
        if '0' <= t <= '9':
            stack_operater.append(t)
        else:
            #연산자면 2개를 꺼내서 계산한다.
            t2 = stack_operater.pop()
            t1 = stack_operater.pop()
            stack_operater.append(cal(t1, t, t2))
    else:
        #결과값 출력
        print('#{} {}'.format(a, stack_operater[0]))