[SWEA][D4][#01224] 계산기3

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

예를 들어

“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
...

My Sol

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

def calc(a, b, op):
    if op == '+':
        return a + b
    elif op == '*':
        return a * b
    elif op == '-':
        return a - b
    elif op == '/':
        return a // b

T = 10
for tc in range(1, T+1):
    N = int(input())
    txt = list(input())
    stack = []
    oper = []

    # 입력연산 각각의 토큰에 대하여
    for t in txt:
        if t ==')':                            # 1. 닫는 괄호가 나온다면
            while oper[-1]!='(':               # oper에서 여는 괄호가 나올 때까지
                op = oper.pop()                # oper에서 하나 추출해서 op에 할당
                b = stack.pop()                # stack에서 하나 뽑아서 b에 할당
                a = stack.pop()                # stack에서 하나 뽑아서 a에 할당
                stack.append(calc(a, b, op))   # op에 맞게 a b 연산해서 stack에 넣기
            oper.pop()                         # ( 여는 괄호 없애줌

        elif t in list(icp.keys()):                   # 2. 연산자가 나온다면
            # oper가 비어있지 않고, oper의 맨 마지막 연산의 스택 내 우선순위가
            # t의 스택 외부 우선순위보다 크거나 같다면
            while oper and isp[oper[-1]] >= icp[t]:
                op = oper.pop()                       # oper에서 여는 괄호가 나올 때까지
                b = stack.pop()                       # stack에서 하나 뽑아서 b에 할당
                a = stack.pop()                       # stack에서 하나 뽑아서 a에 할당
                stack.append(calc(a, b, op))          # op에 맞게 a b 연산해서 stack에 넣기
            oper.append(t)                            # t를 oper에 넣음

        else:                        # 3. 숫자라면
            stack.append(int(t))     # stack에 추가

    print(f'#{tc} {stack.pop()}')

스택에 대한 깊은 이해가 필요한 복잡한 계산기 문제였다. 소괄호의 여닫음이 있어서 이에 대한 추가 처리를 해주어야 하기 때문에 번거로운 문제이다.

각각의 테스트케이스에 대하여 입력한 연산문장 덩어리를 txt로 저장한 뒤, 이 각각의 토큰에 대해 판단을 실시한다. 역시나 숫자라면 stack에 정수형으로 토큰을 형변환하여 추가해준다. 만약 연산자라면 oper 배열에 t를 추가해주는데, 이미 이전에 oper 배열에 여러 연산자가 들어가서 우선순위를 판단해야 한다면 다음과 같이 확인한다. 우선 oper 배열이 빈 배열이 되면 안 되기 때문에 while문의 조건에 oper==True를 넣어주어 빈 스택에서 pop하는 일이 생기지 않도록 한다.

이후 헷갈리는 개념이 isp[oper[-1]] >= icp[t]인데, isp는 스택 내부 우선순위, icp는 스택 외부 우선순위이다. 사칙연산 연산자는 내외부가 같은데 여는 괄호의 경우 스택 외부에서는 우선순위 점수가 3으로 일반 연산자보다 크다. 특히나 헷갈리는 개념은 isp[oper[-1]]이므로 스택 내부 우선순위 점수에 의거하는데, 이는 여는 괄호가 스택 외부에서는 icp에 의해 3점의 강한 우선 순위를 가지며 oper 스택 내부로 들어오면 isp에 의해 최하위 우선순위점수인 0이 되어 이후 들어오는 1점짜리 ‘+’, ‘-‘ 또는 2점짜리 ‘*’, ‘/’를 oper 스택에 쌓을 수 있게 한다.

또한 부등호 역시 엄격하게 확인해주어야 하는데 만약 oper[-1]이 ‘+’인 상황에서 같은 우선순위인 ‘-‘가 들어온다면 stack의 숫자들을 꺼내 oper[-1]인 ‘+’에 대한 연산을 처리해 stack에 넣어야 한다. oper에 1보다 작은 여는 괄호가 나올 때까지나 oper가 빌 때까지 반복해준 뒤 oper에 ‘-‘을 넣어주어야 하는 것이다.

반면 우선순위 점수가 2점으로 높은 편인 ‘*’, ‘/’은 oper에 ‘+’나 ‘-‘가 있더라도 oper에 append할 수 있다. 다만 oper[-1]이 동급인 ‘*’,’\/’라면 2보다 작은 여는 괄호나 +-가 oper[-1]일 때까지 oper에서 연산자를 빼내어 stack의 수들을 처리하여야 한다.

오류를 고려하지 않은 연산들이기 때문에 만약 t가 닫는 괄호 ‘)’ 라면 이전에 분명히 여는 괄고 ‘(‘가 있을 것이다. 이 여는 괄호가 나올 때까지 oper을 빼주어 stack의 수들과 연산한 뒤 stack에 append하는 과정을 반복한다. 왜냐하면 괄호는 연산에서 가장 먼저 연산되어야 하는데 여는 괄호 내부부터 들어온 숫자와 연산자에 대한 처리를 모두 해주어야 괄호 내부에 대한 계산을 해주는 방식이 되기 때문이다. 이후 여는 괄호를 없애주기 위해 while문이 끝나고도 oper.pop()을 한 번 더 해준다.

결과

PASS