힙 구조, 스택 계산기 구현

☑️ To-do

• 힙 정렬 코드 내, heapify 부분 로직 이해
• 스택 계산기 코드 이해

 

• 프로젝트 AWS NBP로 마이그레이션
• 프로젝트 자문 멘토링 
• 소프트웨어 아키텍쳐 고민

 

---

📝 문제

1. 특정 배열의 원소들이 정렬되는 과정을 힙과 배열로 그려 본다.
2. 스택을 활용해 사칙 연산이 가능한 계산기를 구현하는 과정을 공부해본다.

 

---

📄 1번 문제

• 이진 트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
• 완전 이진 트리: 좌우 균형을 이루는 이진 트리

 

 

def heap_sort(arr):
    def down_heap(arr, left, right):
        temp = arr[left]

        parent = left # 왼쪽 노드의 인덱스(부모 노드라고 가정)
        while parent < (right + 1) // 2: # 힙으로 만드려는 범위를 넘어가는 지 검사(자식 노드가 있는 지)
            cl = parent * 2 + 1 # 왼쪽 자식이 들어갈 인덱스
            cr = cl + 1 # 오른쪽 자식이 들어갈 인덱스

            # 자식 노드 중 큰 값을 child에 담는다.
            if cr <= right and arr[cr] > arr[cl]: # left_child < right_child)
                child = cr
            else: # left_child >= right_child || 자식 노드가 하나 인경우
                child = cl

            if temp >= arr[child]: # 부모 노드가 자식 노드보다 큰 경우(힙 상태 OK)
                break

            # 부모 노드가 자식 노드보다 작은 경우(Swap이 필요함)
            arr[parent] = arr[child] # 자식 노드와 부모 노드 위치 swap
            parent = child # 새로운 부모 노드(인덱스) 설정
        arr[parent] = temp

    n = len(arr)

    for i in range((n - 1) // 2, -1, -1): # 절반 위치부터 진행
        down_heap(arr, i, n - 1) # 현재 ~ 마지막 인덱스

        # 정렬된 원소는 뒤에 축적하고 앞에 정렬이 안된 원소들에 대해 다시 힙 정렬 수행
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        down_heap(arr, 0, i - 1)

heap_sort([6, 4, 3, 7, 1, 9, 8])

 

 

output

[6, 4, 3, 7, 1, 9, 8]
[6, 4, 9, 7, 1, 3, 8] 
[6, 7, 9, 4, 1, 3, 8] 
[9, 7, 9, 4, 1, 3, 8] 
[9, 7, 8, 4, 1, 3, 6]

===== 첫 번째 for =====

[6, 7, 8, 4, 1, 3, 9] 
[8, 7, 6, 4, 1, 3, 9]

 

 

 

---

📄 2번 문제

 

💡 계산을 할때, 왜 후위 표기식이 필요한 가?

• 연산 속도가 빠르다.
• 괄호를 쓰지 않고도 우선 계산하여야할 내용을 나타낼 수 있다.

 

calculator.py

import sys

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

def convert_to_postfix(S):
    opStack = ArrayStack()
    answer = ''

    for w in S :
        if w in prec :
            if opStack.isEmpty() :
                opStack.push(w)
            else :
                if w == '(' :
                    opStack.push(w)
                else :
                    while prec.get(w) <= prec.get(opStack.peek()) :
                        answer += opStack.pop()
                        if opStack.isEmpty() : break
                    opStack.push(w)
        elif w == ')' :
            while opStack.peek() != '(' :
                answer += opStack.pop()
            opStack.pop()
        else :
            answer += w

    while not opStack.isEmpty() :
        answer += opStack.pop()

    return answer

def calculate(tokens):
    stack = ArrayStack()
    for token in tokens:
        if token == '+':
            stack.push(stack.pop()+stack.pop())
        elif token == '-':
            stack.push(-(stack.pop()-stack.pop()))
        elif token == '*':
            stack.push(stack.pop()*stack.pop())
        elif token == '/':
            rv = stack.pop()
            stack.push(stack.pop()/rv)
        else:
            stack.push(int(token))
    return stack.pop()

infix = sys.stdin.readline().replace("\\n", "").replace(" ","")

postfix = convert_to_postfix(infix)

print(f"postfix : {postfix}")

result = calculate(postfix)

print(f"result : {result}") 

 

 

🖇️ 계산기 프로그램 작성시 유의점

• 연산자와 피연산자가 구분되어야 한다. (token : 토큰)
• 이항연산자 : 항이 2개 필요
• 단항연산자 : 항이 1개 필요

 

• 표기법
  • infix : 연산자를 중심으로 양쪽에 피연산자가 위치한다.
  • prefix : 연산자가 맨 앞에 오고 피연산자가 연달아 위치한다.
  • postfix : 피연산자가 연달아 위치하고 연산자가 제일 뒤에 위치한다.

 

• infix ⇒ postfix 방법
  1. 연산 순서에 맞게 괄호를 친다.
  2. 연산자의 오른쪽 괄호 다음으로 연산자를 이동시킨다.
  3. 괄호를 지운다.

 

• infix ⇒ postfix 구현을 위한 접근 방법
  • input : +, -, *, /, (, ), 숫자(영문자)로 구성된 infix 수식
    • 연산자 : +, -, *, /, (, )
    • ( : 우선 순위가 제일 낮다고 가정 (무조건 push)
    • ) : 우선 순위가 제일 높다고 가정
  • output : postfix 수식

 

1. 연산자는 스택에 삽입한다.
2. 피연산자의 순서는 그대로다.
3. 연산 순서 중 후순위에 있는 연산자는 스택에서 자신보다 연산 순위가 높은 연산자가 있으면 모두 pop을 한 뒤 스택에 삽입한다.
4. 더이상 연산자가 존재하지 않을 때는 스택에 존재하는 모든 연산자들에 대해 차례차례 pop연산을 수행한다.

⚠️ 오른쪽 괄호가 등장할 때는 왼쪽 괄호 이후의 연산자들을 모두 pop한다.

 

 

🏃🏻 구현

1️⃣ infix → postfix

• out_stack : postfix 연산방식을 담는 리턴 리스트
• operand_stack : 연산자를 넣었다 뺐다 하는 스택
• Pseudo - code

for each token in expression:
        if token == 피연산자(operand):
                out_stack.append(token)
        if token == '(':
                out_stack.push(token)
        if token == ')':
                operand_tack에서 '('가 나올 때까지 모든 연산자들을 pop
                out_stack에 append
        if token in '+*-/':
                operand_stack내의 연산자들과 token의 우선순위 비교 후, pop, push 수행

operand_stack에 남은 연산자를 모두 pop하고 out_stack에 추가한다.

 

 

2️⃣ postfix → 계산

 

 

 

• result_stack : 후위 연산 결과를 저장하는 스택
• Pseudo - code

for each token in out_stack:
        if token == 피연산자(operand):
                result_stack.append(token)
        if token in '+*-/':
                a = result_stack.pop()
                b = result_stack.pop()
                [b], [token], [a] 순으로 계산한 결과를 result_stack에 삽입

result_stack에 남아있는 마지막 값을 리턴한다.

 

 

 

---

🔗 Reference

• 표기법. infix, prefix, postfix. 개요와 간단예제.
• (https://kcoder.tistory.com/entry/표기법-infix-prefix-postfix-개요와-간단예제)
• 자료구조 스택 활용 - 계산기
• (https://www.youtube.com/watch?v=G9ujrSGEB4A&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=11)