Python 심화 - 3

2019-03-13

ADT(Abstract Data Type)

추상 자료형
operation의 list(내부 구조체는 나열하지 않음)

어떤 자료구조가 가지고 있는 operation(함수)의 나열(블록)
함수 signature(interface)만 나열할 뿐 내부 구현을 표시하지 않음 - 추상화
operation(함수)의 작동 방식 설명

Stack and Queue

데이터를 일시적으로 저정할 때 많이 사용
- Stack
  - LIFO(Last In First Out)
  - 후입선출
  - 나중에 들어온 것이 제일 먼저 나가는 방식
  - ex) 접시 쌓기
  1. linked list
  2. python list - 기초 자료구조
자료구조에 반드시 포함되어야 할 것 - insert, search, delete

Coding Practice

후위 표기법을 이용한 정수형 계산기 만들기

3*5 처럼 연산자가 중간에 있는 경우를 중위 표기법이라고 한다.
*35 처럼 연산자가 앞에 있는 경우를 전위 표기법이라고 한다.

35* 처럼 연산자가 뒤에 있는 경우를 후위 표기법이라고 한다.

후위 표기법

- 컴퓨터가 계산하기 쉬운 수식
- 괄호가 없다.
- 연산자가 뒤에 위치

[ 후위 표기법 적용 예 ]

(3 + 2 * 2 - 4) * 3 + 2 * (5 - 7) = 322 * + 4 - 3 * 257 - * +
5 * 7 - 5 / 3 + 2 + 5 * 3 = 57 * 53 / - 2 + 53 * +
7 - 3 * 5 / 2 + (3 * 5 - 2 * 3) = 735 * 2 / - 35 * 23 * - +
6 * (5 - 2 * 3) - (3 * 2 + 3 / 2 + 1) = 6523 * - * 32 * 32 / + 1 + -

입력 시 피연산자는 1자리로 한다.
- 연산자(Operator) : 연산을 수행하는 기호
- 피연산자(Operand) : 연산에 참여하는 변수나 상수
정수 연산이므로 ‘//‘ 사용
stack 사용
후위 표기법으로 만드는 법
- 최종 후위 수식을 담을 수식 리스트와 연산자를 가중치에 따라 담을 스택 리스트 필요
- 각 연산자마다 가중치를 두어야 함
  - 1순위 : *, /
  - 2순위 : +, -
  - 3순위 : (, )
- 수식 리스트에는 피연산자를 무조건 넣는다.
- 연산자를 만나면 스택 리스트에 들어가는데 다음과 같은 규칙이 있다.
  - “(“는 스택 리스트에 연산자가 있건 없건 무조건 넣는다.
  - 연산자를 넣을 때, 가중치가 높으면 무조건 넣는다.
  - 가중치가 같으면 그 전에 쌓여있던 연산자를 빼서 수식 리스트에 넣는다.
  - 넣는 연산자 가중치가 작을 경우, 그 전에 쌓여있던 연산자를 빼서 수식 리스트에 넣는다.
  - 그 다음으로 넣을 때에도 가중치 비교를 계속해서 넣는다.
  - “)”를 만나면 “(“ 위에 쌓여 있는 모든 연산자를 수식 리스트에 넣는다.
함수를 구현할 때 하나의 함수로 끝내는 것은 좋지 않다.

기능을 가지고 있는 함수를 여러 개 만들어서 절차 지향적으로 실행하도록 한다.

class Stack:

    def __init__(self):
        self.container = list()
        
    def empty(self):
        if not self.container:
            return True
        else:
            return False
        
    def push(self, data):
        self.container.append(data)
        
    def pop(self):
        return self.container.pop()
   
    def peek(self):
        return self.container[-1]


def get_weight(opr):
    """
    get_weight(string) --> int
    연산자 비교를 위해 정수형 값을 반환
    """
    if opr == '*' or opr == '/':
        result = 2
        
    elif opr == '+' or opr == '-':
        result = 1
       
    elif opr == '(' or opr ==')':
        result = 0
        
    return result


def conv_pfx(exp):
    """
    conv_pfx(string) --> string
    연산자와 피연산자를 후위표기법으로 변환
    """
    re_exp = exp.replace(' ', '')
    
    listExp = []
 
    oprStk = Stack()
    
    for i in range(len(re_exp)):           
        if re_exp[i] == '*' or re_exp[i] == '/' or re_exp[i] == '+' or re_exp[i] == '-':
          
            if oprStk.empty(): 
                oprStk.push(re_exp[i])
                
            else:
                while get_weight(re_exp[i]) <= get_weight(oprStk.peek()):
                   
                    listExp.append(oprStk.pop())
                    
                    if oprStk.empty():
                        break
                        
                oprStk.push(re_exp[i])
                
        elif re_exp[i] == '(':
            oprStk.push(re_exp[i])
            
        elif re_exp[i] == ')':
            while not oprStk.peek() == '(':
               
                listExp.append(oprStk.pop())
                
            oprStk.pop()
            
        else:
            listExp.append(re_exp[i])

        if i == len(re_exp) - 1:
            
            while not oprStk.empty():
                
                listExp.append(oprStk.pop())
                
    return ''.join(listExp)


def operator(f_num, l_num, opr):
    """
    operator(int, int, string) --> int
    연산자에 따라 연산을 수행하여 정수형 반환
    """
    if opr == '*':
        return f_num * l_num
   
    elif opr == '/':
        return f_num // l_num
    
    elif opr == '+':
        return f_num + l_num
    
    elif opr == '-':
        return f_num - l_num


def calculator(exp):
    """
    calculator(string) --> int
    문자열 수식을 넣으면 결과값을 정수형으로 반환
    """
    pfx_exp = conv_pfx(exp)
    
    oprStk = Stack()
    
    for i in range(len(pfx_exp)):
 
        if pfx_exp[i] == '*' or pfx_exp[i] == '/' or pfx_exp[i] == '+' or pfx_exp[i] == '-':
            
            l_num = int(oprStk.pop())
            f_num = int(oprStk.pop())
           
            oprStk.push(str(operator(f_num, l_num, pfx_exp[i])))
          
        else:
            oprStk.push(pfx_exp[i])
           
        if i == len(pfx_exp) - 1:
            
            result = int(oprStk.pop())
            
    return result


# 계산기 테스트
exp1 = '(3 + 2 * 2 - 4) * 3 + 2 * (5 - 7)'
print(conv_pfx(exp1))
print(calculator(exp1))
>> 322*+4-3*257-*+
   5

exp2 = '5 * 7 - 5 / 3 + 2 + 5 * 3'
print(conv_pfx(exp2))
print(calculator(exp2))
>> 57*53/-2+53*+
   51

Computer Engineering

Hardware Architecture Keywords
- CPU의 구조
  1. ALU(Arithmetic Logic Unit)
    - 산술논리연산 장치
    - +, -, *, / 등의 정수 연산을 수행하는 유닛(가산기, 보수기, 쉬프터)
  2. CU(Control Unit)
    - 제어 장치
    - 명령어 해석과 실행을 담당하는 유닛
  3. FPU(Floating Point Unit)
    - 부동소수점 장치
    - 실수 연산을 담당하는 유닛
    - CPU에서는 1개만 존재
    - 그래픽 카드에는 FPU만 존재한다. 수많은 FPU를 병렬로 빠르게 계산할 수 있게 한다.
  4. Register(레지스터)
    - CPU의 메모리
    - Program Counter(PC, Instruction Pointer), EIP
    - Instruction Register(IR)
    - Stack Pointer
    - Base Pointer(Frame Pointer), EBP
    - General Purpose Register(EAX, EBX, ECX…)
    - Register를 알아야 Context Switching 기법을 이해할 수 있다.
- Memory Hierarchy(메모리 계층)
  1. Register
  2. Cache
    - cache hit, cache miss
    - Principle of locality
  3. Main memory(RAM)
  4. Hard Disk(HDD), Soild State Disk(SSD)
- Memory Layout(Segment)
  - 각 영역에 변수가 들어간다.(메모리, 데이터)
    1. Code Segment
    2. Data Segment
    3. Stack Segment
    4. Heap Segment
  - stack은 빠르고 heap은 느리다.
  - page, page fault
- 가상 메모리(OS + 아키텍처)

지눅쿠의 개발 블로그

StudyPython and CE

Python 심화 - 3

ADT(Abstract Data Type)

Stack and Queue

Coding Practice

Computer Engineering