[SWEA] 1224번 계산기3 - 파이썬

📒 문제

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

예를 들어

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

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

"345+6*+7+"

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

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

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

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

입력

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

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

출력

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

✏️ 풀이

후위표기법을 익히는게 사실 제일 헷갈렸다.
그 부분을 제외하면 구현부분은 말그대로 '구현'하는 것이기 때문에 어렵진 않았는데,
작성한 코드는 후위표기법 변환과정이 조금 노가다성이 있다.

for tc in range(10):
    N = int(input())
    s = input()
    tokens = []
    stack = []
    result = []

    # 후위표기법 적용
    for i in range(N):
        if s[i].isdigit():
            tokens.append(int(s[i]))
        else:
            if s[i] == ')':
                chk = ''
                while chk != '(':  # '('를 찾을 때까지
                    chk = stack.pop()
                    tokens.append(chk)
                tokens.pop()  # tokens의 마지막에 '('가 들어가버렸으므로
                continue
            elif s[i] == '*':
                while stack and stack[-1] == '*' and stack[-1] != "(":  # '('는 '*'로 뽑아낼 수 없다.:
                    tokens.append(stack.pop())
            elif s[i] == '+':
                while stack and stack[-1] != "(":  # '('는 '+'로 뽑아낼 수 없다.
                    tokens.append(stack.pop())
            stack.append(s[i])

    while stack:  # stack이 비어있지 않을 수 있기 때문
        tokens.append(stack.pop())

    # 계산
    for i in tokens:
        if i in range(0, 10):
            result.append(i)
        else:
            if i == "+":
                p1 = result.pop()
                p2 = result.pop()
                result.append(p2 + p1)
            elif i == "*":
                p1 = result.pop()
                p2 = result.pop()
                result.append(p2 * p1)

    print(f'#{tc+1} {result[-1]}')

하지만 이러한 코드도 다른 조금은 짧은 코드들과 비슷한 시간을 출력하는 것을 보고 놀랐다.
생각보다 효율성이 나쁘진 않았구나..싶다.

우선순위를 적용한 풀이법도 존재하는데,
이 부분은 추후 추가하도록 할 것이다. (새로 풀어보는데로!!)