[파이썬] 스택(Stack) 알고리즘 정리 - 계산기 구현하기

stack으로 계산기 구현하기

why 계산기 구현?

• 중위 표기법 수식을 스택을 이용하여 후위 표기법으로 변경할 수 있음
• 계산기 입장에서 계산이 쉬워져 속도 ↑

중위 표기법

• 연산자를 피연산자의 가운데에 표기하는 일반적인 방법
• ex) A+B , 2+3*4,
• 인간에게 친숙한 표현법

반응형

후위 표기법

• 컴퓨터의 입장에서 중위 표기법보다 후위 표기법이 더 쉬움
• 연산자가 나오면 이전 숫자 2개와 연산을 하는 방식
• ex) 2 3 4*+ → 2 12 + → 14의 과정으로 계산
• A*B-C/D을 후위 표기법으로 변환 방법
  1. ((A*B)-(C/D)) // 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현
  2. ((AB)*(CD)/)- // 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동
  3. AB*CD/- // 괄호 제거

변환 과정

1. 입력 받은 중위표기식을 읽음
2. 읽은 표기식이 피연산자이면 피연산자 출력
3. 읽은 표기식이 연산자(괄호포함)일 경우 우선순위에 따라 분류
   1. 우선 순위가 높으면 → 스택에 psuh
   2. 우선 순위가 낮으면 → 연산자의 우선순위가 읽은 표기식의 우선순위보다 작아질 때까지 스택에서 pop한 후 연산자를 push
   3. 만약 top에 연산자가 없을 경우 → push
4. 읽은 표기식이 )일 경우
   1. 스택 top에 (가 올 때까지 스택에 pop 수행
   2. pop한 연산자 출력
   3. (를 만나면 pop만 하고 출력하지 않음
5. 중위표기식에 더 읽을 것이 없을 때까지 반복
6. 스택에 남아 있는 연산자를 모두 pop하여 출력 (스택 밖 (가 우선 순위가 가장 높고 스택 안의 (가 우선 순위가 가장 낮음)

중위표기법을 후위 표기법으로 바꾸기 위한 코드

def suf_change(n) :
    stack = []
    result = ''
    for i in n:
        if i == '+' or i == '-': #우선순위 1 / 1
            while stack and stack[-1] != '(':
                result += stack.pop()
            stack.append(i)
        elif i == '*' or i == '/': #우선순위 2 / 2
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                result += stack.pop()
            stack.append(i)
        elif i == '(': #우선순위 0 / 3
            stack.append(i)
        elif i == ')': #(를 만날때까지 모두 pop
            while stack and stack[-1] != '(':
                result += stack.pop()
            stack.pop()
        else:
            result += i

    while stack:
        result += stack.pop()
    return result

print(suf_change(input()))

후위표기법 계산기 구현 코드

def Calculation(x):
    stack = []
    for i in x:
        if i == '+':
            stack.append(stack.pop()+stack.pop())
        elif i == '-': 
            stack.append(-(stack.pop()-stack.pop()))
        elif i == '*': 
            stack.append(stack.pop()*stack.pop())
        elif i == '/': 
            divide = stack.pop()
            stack.append(stack.pop()/divide)
        else:
            stack.append(int(i))
    return stack.pop()

—> eval() 내장 함수를 이용하여 계산할 수도 있음