초보몽키의 개발공부로그

강의노트 21. 자료구조 - stack을 이용한 후위표기법 계산기 만들기

18 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

후위표기법(postfix notation)

  • 수업자료
  • 연산자를 피연산자의 뒤에 놓는 방법 (사람이 사용하는 수식의 표기 방법 - 중위(infix) 표기법)
  • 괄호가 없어도 계산 순서가 일정하다.
  • 컴퓨터에서의 수식의 계산은 (1) 수식을 후위표기식으로 바꾸고 (2) 후위표기식을 계산하는 두 과정으로 이루어진다.
views
출처 : https://github.com/ythwork

후위표기법 만들기

  • 상세 내용은 상기 수업 자료를 참고한다.

준비물

  1. listExp : 최종 후위 수식을 담을 리스트
  2. stack : LIFO 방식의 자료구조, 연산자를 가중치에 따라서 담을 스택 리스트

연산자 우선순위

  1. *, / : 제일 크다
  2. +, - : 두번째
  3. ( :가장 작다

규칙

  • 중위표기법 : (2 + 5) * 3 * (2 + 1) ==> 후위표기법: 25 + 3 * 21 + *
  • 숫자가 오면 listExp 에 담는다.
  • 숫자가 아닌 연산자는 stack에 쌓는다.
  • stack 의 맨 위 연산자의 가중치가 새로 추가되는 연산자의 가중치 보다 높거나 같다면 listExp로 옮긴다.
  • ( 는 가중치에 상관 없이 무조건 stack에 쌓는다.
  • )를 만나는 순간 ( 위에 있는 모든 연산자를 listExp에 pop 으로 넣고 ( 는 없앤다.

stack을 이용한 후위표기법 계산기 만들기

ADT 인터페이스

Data

org_exp # 중위표기법 (유저에게 입력 받으며 공백을 삭제하여 저장한다)
postfix_exp # 후위표기법 (유저에게 입력 받은 중위 표기법을 후위 표기법으로 변경하여 저장한다.)

Opertion

.get_weight(self, oprt)
# 인자로 받은 연산자의 가중치를 리턴한다.
# 가중치 순서 : *, / > +, - > (

.convert_to_postfix(self)
# 인스턴스 변수 org_exp를 후위표기법으로 변경하여 postfix_exp 변수에 저장한다.
# 가중치에 따라서 연산자를 담을 스택과, 최종 후위 수식을 담을 리스트를 활용한다.

.get_postfix_exp(self)
# postfix_exp 변수에 담긴 값을 리턴한다. 없다면 convert_to_postfix()을 실행한다.

.calc_two_oprd(self, 피연산자1, 피연산자2, 연산자)
# 연산자의 종류에 따라서 연산을 진행한 결과를 리턴한다.

.calculate(self)
# postfix_exp 변수에 담긴 후위수식 값을 연산한 결과를 리턴한다.

구현코드

from stack import Stack

class Calculator:
    def __init__(self, org_exp):
        self.org_exp = org_exp.replace(' ', '')
        self.postfix_exp = None

    def get_weight(self, oprt):
        if oprt == '*' or oprt == '/':
            return 9
        elif oprt == '+' or oprt == '-':
            return 7
        elif oprt == '(':
            return 5
        else:
            return -1

    def convert_to_postfix(self):
        exp_list = []
        oprt_stack = Stack()

        for ch in self.org_exp:
            if ch.isdigit():
                exp_list.append(ch)
            #연산자라면
            else:
                #'(' or 연산자 스택이 비었다면
                if ch == '(' or oprt_stack.is_empty():
                    oprt_stack.push(ch)
                #')'
                elif ch == ')':
                    op = oprt_stack.pop()
                    while op != '(':
                        exp_list.append(op)
                        op = oprt_stack.pop()
                #'+', '-', '*', '/' : 가중치가 높을 때
                elif self.get_weight(ch) > \
                    self.get_weight(oprt_stack.peek()):
                    oprt_stack.push(ch)
                #'+', '-', '*', '/' : 가중치가 낮거나 같을 때
                else:
                    while oprt_stack and self.get_weight(ch) <=\
                          self.get_weight(oprt_stack.peek()):
                        exp_list.append(oprt_stack.pop())
                    oprt_stack.push(ch)
        while oprt_stack:
            exp_list.append(oprt_stack.pop())
        self.postfix_exp = ''.join(exp_list)

    def get_postfix_exp(self):
        if not self.postfix_exp:
            self.convert_to_postfix()

        return self.postfix_exp

    def calc_two_oprd(self, oprd1, oprd2, oprt):
        if oprt == '+':
            return oprd1 + oprd2
        elif oprt == '-':
            return oprd1 - oprd2
        elif oprt == '*':
            return oprd1 * oprd2
        elif oprt == '/':
            return oprd1 // oprd2

    def calculate(self):
        oprd_stack = Stack()

        for ch in self.postfix_exp:
            if ch.isdigit():
                oprd_stack.push(int(ch))
            #연산자라면
            else:
                oprd2 = oprd_stack.pop()
                oprd1 = oprd_stack.pop()
                oprd_stack.push(self.calc_two_oprd(
                    oprd1, oprd2, ch))
        return oprd_stack.pop()

if __name__ == "__main__":
    a = input("수식을 입력하세요 : ")
    calc = Calculator(a)
    print(calc.get_postfix_exp())
    print("{exp} = {result}".format(
        exp = calc.org_exp, result = calc.calculate()))

강의노트 20. 자료구조 - queue (큐)

18 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

queue

  • 참고글
  • 참고글-큐와 스택의 실제 사용 예
  • stack과 queue는 search가 없다.
  • FIFO (First Input First Out, 선입선출, 파이포)
  • Rear에서 삽입, Front에서 삭제가 발생
  • 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.(위키피디아)
  • queue overflow : 큐가 꽉 차서 더이상 자료를 넣을 수 없는 경우
  • queue underflow : 큐가 비어 있어 자료를 꺼낼 수 없는 경우
views
views

queue ADT (인터페이스)

  • front(head) : 데이터를 dequeue 할 수 있는 위치
  • rear(tail) : 데이터를 enqueue 할 수 있는 위치
  • 메소드
    • is_empty() -> boolean
    • enqueue -> insert
    • dequeue -> delete
    • peek -> 엿보기 : 맨 앞의 값 반환만 하고 삭제는 안함

queue 구현 예시1 (python list 사용)

class Queue(list):
    # enqueue == > insert 관용적인 이름
    enqueue = list.append
    # dequeue == > delete
    def dequeue(self):
        return self.pop(0)

    def is_empty(self):
        if not self:
            return True
        else:
            return False

    def peek(self):
        return self[0]

if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)

    while not q.is_empty():
        print(q.dequeue(), end= ' ') # 1 2 3 4 5

queue 구현 예시1 (node를 사용한 queue)

  • 면접에서는 node를 활용한 구현 필요
  • head,tail 만 있어도 구현이 된다
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        if not self.head:
            return True

        return False

    def enqueue(self, data):
        new_node = Node(data)

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return None

        ret_data = self.head.data
        self.head = self.head.next
        return ret_data

    def peek(self):
        if self.is_empty():
            return None

        return self.head.data

테스트코드

if __name__ == "__main__":
    q = Queue()

    print(q.is_empty()) # True

    q.enqueue(1)
    print("deleted data : {}".format(q.dequeue())) # deleted data : 1

    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)

    while not q.is_empty():
        print(q.dequeue()) # 2, 3, 4, 5

강의노트 19. 자료구조 - stack (스택)

18 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

stack

  • 수업자료
  • 참고자료
  • 참고글-큐와 스택의 실제 사용 예
  • stack과 queue는 search가 없다.
  • LIFO (Last Input First Out, 선입후출, 라이포)
  • 데이터 저장소에서 새로 들어오는 데이터의 위치가 저장소의 끝 부분(Top 혹은 Top pointer라고 한다)이고, 내보내는 데이터 역시 저장소의 Top에서 나간다. 입력은 push, 출력은 pop이다. peek는 Top의 위치에 있는 데이터를 확인하는 것을 말한다.
views

ADT(abstract data type) 추상 자료형

  • 참고 추상자료형-위키피디아
  • 참고 추상자료형
  • 기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것을 추상 자료형이라고 한다
  • 메소드의 목록 (인터페이스)
  • 추상 자료형은 구현자와 사용자를 분리해 준다. 라이브러리를 가져다 쓰거나 내장 함수를 사용하는 것도 추상 자료형이 정의되어 있기 때문이다. 또한 추상 자료형에 대한 구현은 외부로 부터 숨겨져 정보 은닉(Information Hiding)이 이루어지게 된다. (출처)

stack ADT (인터페이스)

  • is_empty() -> boolean
  • push -> insert : push(data)
  • pop -> delete : pop return 맨위 값을 리턴하고 동시에 삭제
  • peek -> 엿보기 : 맨 위 값 반환만 하고 삭제는 안함

stack 구현 예시1 (python list 사용)

# Stack 클래스 정의 - python list 활용
class Stack(list):
    push = list.append    # Insert
                          # Delete - 내장 pop 메소드 활용
    def is_empty(self):   # 데이터가 없는지 확인
        if not self:
            return True
        else:
            return False

    def peek(self):        # 최상단 데이터 확인
        return self[-1]

if __name__=="__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)

    while s:
        data = s.pop()
        print(data, end=' ') # 3 2 1

stack 구현 예시2 (node 사용)

  • 면접에서는 node를 사용한 stack 구현이 자주 출제된다.
  • head만 있어도 구현이 가능하다.
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    def is_empty(self):
        if not self.head:
            return True

        return False

    def push(self, data):
        new_node = Node(data)

        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.is_empty():
            return None

        ret_data = self.head.data

        self.head = self.head.next

        return ret_data

    def peek(self):
        if self.is_empty():
            return None

        return self.head.data

if __name__ == "__main__":
    s = Stack()

    print(s.is_empty()) # True

    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)

    print("peek of data : {}".format(s.peek())) # 5

    while not s.is_empty():
        print(s.pop()) # 5, 4, 3, 2, 1

170418_TIL

18 Apr 2017 | TIL

오늘 한 일 (회고)

  • 컴퓨터공학 입문 수업을 들었다.
    • stack을 이용한 후위표기법 계산기 구현
    • tree
    • heap
  • Node를 사용하여 stack 을 구현해보았는데 생각보다 시간이 많이 걸렸다.

내일 할 일

  • linked list 복습
  • queue 복습 및 Node를 사용하여 구현해보기
  • stack을 이용한 후위표기법 계산기 구현방법 복습
  • 배열을 사용하여 heap 구현해보기 (숙제)

강의노트 18. 자료구조 - LinkedList (링크드 리스트)

17 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

linked list

  • 강의자료
  • 참고 생활코딩 - linked list
  • 자료구조에서 가장 중요한 개념 중 하나 (doubly-linked-list와 함께 면접에 자주 나온다. node를 사용하여 구현)
  • Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것
  • linked list에서 가장 중요한 것은 연결이 무엇인가를 파악하는 것
  • python 의 경우 list 기본 자료형에 linked list 기능이 함께 포함되어 있다.
  • array list에서는 엘리먼트라는 이름을 사용했지만 linked list와 같이 연결된 엘리먼트들은 노드(node, 마디, 교점의 의미) 혹은 버텍스(vertex, 정점, 꼭지점의 의미)라고 부른다.
views
linked list (출처 : wikipedia)


views
linked list (출처 : wikipedia)


views
doubly-linked-list (출처 : wikipedia)


dummy linked list

  • 맨 앞에 dummy를 두어서 if문의 양을 줄인다.
  • (실제 데이터를 지닌 노드가 아닌, 구현의 편의를 위해서 맨 앞에 두는 무의미한 노드)
  • 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.

Node

  • 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다
  • 자료구조를 이해하기 위해서는 노드에 충분히 익숙해져야 한다.
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

dummy linked list ADT (인터페이스)

views
출처 : https://github.com/ythwork/
  • 링크드 리스트 클래스 내에는 노드를 가르키는 1) 4개의 참조와 2) 데이터의 개수 만 존재한다.
  • head : 맨 앞을 가르킨다.
  • before : 현재 위치 전
  • current : 현재 탐색위치
  • tail : 맨 뒤를 가르킨다.
  • num_of_data : 데이터의 총 개수
  • 메소드 구현
    • 생성자 : head, before, current, tail, num_of_data 초기화
    • .append() : 맨 뒤에 노드 추가 (insert)
    • .first() : 맨 앞의 노드 검색 (search)
    • .next() : 다음 노트 검색 (search)
    • .delete() : 현재 노드의 삭제 (delete)

dummy linked list 구현예시

LinkedList Class 정의

# Node 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


# LinkedList 클래스 (자료구조) 정의
class LinkedList:

    # 초기화 메소드
    def __init__(self):
        dummy = Node("dummy")
        self.head = dummy
        self.tail = dummy

        self.current = None
        self.before = None

        self.num_of_data = 0

    # append 메소드 (insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경)
    def append(self, data):
        new_node = Node(data)
        self.tail.next = new_node
        self.tail = new_node

        self.num_of_data += 1

    # delete 메소드 (delete - current 노드 삭제, 인접 노드의 current, next 변경, 데이터 개수 변경)
    def delete(self):
        pop_data = self.current.data

        if self.current is self.tail:
            self.tail = self.before

        self.before.next = self.current.next
        self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.
        #

        self.num_of_data -= 1

        return pop_data

    # first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
    def first(self):
        if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
            return None

        self.before = self.head
        self.current = self.head.next

        return self.current.data

    # next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
    def next(self):
        if self.current.next == None:
            return None

        self.before = self.current
        self.current = self.current.next

        return self.current.data

    def size(self):
        return self.num_of_data

테스트 코드

if __name__ = '__main__':
  l_list = LinkedList()
  l_list.append(5)
  l_list.append(2)
  l_list.append(1)
  l_list.append(2)
  l_list.append(7)
  l_list.append(2)
  l_list.append(11)

  print('first :', l_list.first())      # first : 5
  print('next :', l_list.next())        # next : 2
  print('size :', l_list.size())        # size : 7
  print('delete :', l_list.delete())    # delete : 2
  print('size :', l_list.size())        # size : 6
  print('current:', l_list.current.data)# current: 5
  print('tail:', l_list.tail.data)      # tail: 11
  print('first :', l_list.first())      # first : 5
  print('next :', l_list.next())        # next : 1
  print('next :', l_list.next())        # next : 2
  print('next :', l_list.next())        # next : 7


  # 전체 노드 data 표시하기
  data = l_list.first()

  if data:
      print(data, end=' ')
      while True:
          data = l_list.next()
          if data:
              print(data, end= ' ')
          else:
              break
  # 5 1 2 7 2 11



  # 2만 삭제하기
   data = l_list.first()

   if data and data == 2:
       l_list.delete()
       print('deleted', end=' ')
   else:
       print(data, end= ' ')

   while True:
       data = l_list.next()
       if data == 2:
           l_list.delete()
           print('deleted', end=' ')
       elif data:
           print(data, end=' ')
       else:
           break

   # 5 1 deleted 7 deleted 11