[SWEA] 1224 [S/W 문제해결 응용] 6일차 - 계산기3 (파이썬 python)

 

 

문제 링크

 

 

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

SW Expert Academy

 

 

 

문제 풀이

 

 

for tc in range(1, 11):
    length = int(input())
    exp = list(map(str, input()))
    postfix = []
    stack = []
    stack_cal = []
    prior = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    for e in exp:
        if e.isdigit():
            postfix.append(e)
        elif e == '(':
            stack.append(e)
        elif e == ')':
            while stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()
        else:
            while stack and prior[e] <= prior[stack[-1]]:
                postfix.append(stack.pop())
            stack.append(e)
    while len(stack) != 0:
        postfix.append(stack.pop())

    for p in postfix:
        if p.isdigit():
            stack_cal.append(int(p))
        elif p == '+':
            a = stack_cal.pop()
            b = stack_cal.pop()
            stack_cal.append(a + b)
        elif p == '-':
            a = stack_cal.pop()
            b = stack_cal.pop()
            stack_cal.append(a - b)
        elif p == '*':
            a = stack_cal.pop()
            b = stack_cal.pop()
            stack_cal.append(a * b)
        elif p == '/':
            a = stack_cal.pop()
            b = stack_cal.pop()
            stack_cal.append(a / b)
    print("#{} {}".format(tc, stack_cal.pop()))

 

 

연산자에 대한 우선순위를 먼저 저장해둔다

첫 번째 for문은 주어진 계산식을 후위 표기식으로 변환하는 과정이다!

주어진 계산식을 리스트화하여 하나씩 값을 빼내어 그 값이

1) 만약 숫자일 경우 바로 후위표기식에 대한 리스트(postfix)에 넣어준다

2) 만약 여는 괄호 '('일 경우 연산자들을 넣어두는 stack에 넣어준다

3) 닫는 괄호 ')'가 나왔을 경우 stack에 저장된 연산자들을

다시 여는 괄호가 나올 때까지 모두 빼서 후위표기식 리스트에 넣어준다

4) 그 외의 연산자가 나왔을 경우

stack에 들어있는 것과 우선순위를 비교하여 더 낮을 경우

stack에 있는 연산자들을 먼저 pop 해주어 후위 표기식 리스트에 넣어준다

그 다음 리스트에서 나온 연산자를 넣어준다

 

마지막으로 스택에 남은 모든 연산자들을

후위표기식 리스트에 넣어주면 후위표기식이 완성된다

 

 

두 번째 for문에서는 후위표기식을 계산한다

새롭게 계산을 위한 스택(stack_cal)을 생성한다

 

후위표기식 리스트에서 하나씩 꺼내어

1) 숫자가 나올 경우 stack_cal에 넣어주고

2) 연산자가 나올 경우 앞서 stack_cal에 넣어둔 숫자들을 pop()으로 빼내어

연산자에 맞는 연산을 실행한 후 다시 스택에 넣어준다

 

이 과정이 끝나면 stack_cal에는 후위 표기식의 계산 결과만 남게 된다