[SWEA][D4][#01223] 계산기2

출처

• SW Expert Academy

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

문제

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

예를 들어

“3+4+5*6+7”

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

“34+56*+7+”

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

문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 피연산자인 숫자는 0 ~ 9의 정수만 주어진다.

입력

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

총 10개의 테스트 케이스가 주어진다.

출력

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

예제

입력

101
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
79
4+4*3*4*9+2+7*4*7+7*7*9*5*2+8*8+2*6*7*3*7*9*3*4+8+8*9+3+9+6+9+4*1+6*3+5+1+7+5*1
...

출력

#1 28134
#2 195767
...

My Sol

icp = isp = {'+':1, '*':2}

for tc in range(10):
    N = int(input())
    oper = []
    fix = []

    # 후위 표기법으로 변경
    txt = input()
    for t in txt:
        if t in icp:
            while oper and isp[oper[-1]] >= icp[t]:
                fix.append(oper.pop())
            oper.append(t)
        else:
            fix.append(t)

    while oper:
        fix.append(oper.pop())

    # 계산하면서 stack 비우기
    stack = []
    for t in fix:
        if t in icp:
            b = int(stack.pop())
            a = int(stack.pop())

            if t =='+':
                stack.append(a+b)
            elif t == '*':
                stack.append(a*b)

        else:
            stack.append(t)

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

우선순위를 미리 딕셔너리로 지정하는데, 괄호의 경우 스택 밖에서는 3으로 가장 큰 우선순위를 가지나, 스택 안에서는 0으로 가장 작은 우선순위를 가지기 때문에 스택 밖의 우선순위인 icp와 스택 안의 우선순위인 isp를 구분한다. 하지만 본 문제는 +와 *만 있으므로 굳이 구분할 필요는 없지만, 연습을 위해 icp와 isp를 지정하였다.

스택을 이용해 계산을 처리하려면 인간친화적인 중위표기법을 컴퓨터친화적인 후위표기법으로 변형한 뒤, 이를 하나하나 떼어내어 별도의 스택에서 연산을 처리하면서 하나의 값만 남기게 된다. 이를 출력하면 되겠다.

먼저 중위표기법을 후위표기법으로 바꾸는 방법에 대해 알아보겠다. 입력받은 연산 덩어리를 txt에 저장한 뒤, 하나하나 떼어낸 것을 t라고 하며 for문을 돌린다. token이라고 하는데 편의상 t만 쓰겠다. 연산자를 oper, 피연산자 및 처리된 연산/피연산자를 fix 리스트에 담을 것이다. 각 t에 대하여 icp, 즉 연산자인지 확인하여 아니라면 fix에 추가해주면 된다. 만약 연산자에 해당한다면, 우선순위에 따라 연산자를 얼마나 뽑아낼지를 결정하게 되는데, 우선 oper 리스트, 즉 연산자가 들어있는 리스트가 비게되면 반복을 중지하는 조건을 깔고, isp[oper[-1]], 즉 현재 oper에 들어있는 연산자의 제일 최신 연산자의 우선순위가 현재 token 연산자의 우선순위보다 크거나 작으면 그냥 oper에 t 연산자를 추가하면 된다.

만약 t가 ‘+’라면 icp에 의해 우선순위 점수가 1이므로 oper에 어떤 것이 들어있든 1보다 크거나 같기 때문에 oper가 빌 때까지 계속 연산자를 출력해낼 것이다. t가 ‘*‘라면 oper에 ‘+’가 나올 때까지 oper.pop()을 fix에 append할 것이다. 이렇게 fix 리스트에 후위표기법에 대한 순서로 t들이 배치되었다.

이제는 후위표기법 리스트인 fix를 다른 스택에 옮겨가며 연산을 실시해보자. 다른 별도의 스택을 그냥 stack이라고 이름 짓고, fix의 각 t에 대하여 icp에 속하는지 여부를 확인한다. 이는 곧 연산자인지 확인하는 것이다. 만약 연산자가 아닌 숫자 등의 피연산자라면 stack에 append하면 되고, 연산자라면 stack에서 뒤에서 하나씩 뽑아서 연산자에 맞게 연산하고 이 결과를 stack에 다시 append하는 것이다.

이 과정을 모두 거치면 stack에는 최종 결과값 1개만 남게 되고, 이를 pop() 해서 출력 형식에 맞게 출력하면 되겠다.

결과

PASS