자료구조와 알고리즘 - 2 link
10강. 양뱡향 연결 리스트(Doubly Linked Lists)
노드간 참조공간을 뒤따라 오는 개체 참조 외에도 앞서오는 개체 참조공간도 생성하여
앞에서 뒤로, 뒤에서 앞으로 링크가 되어있는 형태
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def __repr__(self):
if self.nodeCount == 0:
return 'LinkedList: empty'
s = ''
curr = self.head
while curr.next.next:
curr = curr.next
s += repr(curr.data)
if curr.next.next is not None:
s += ' -> '
return s
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
실습1
목표: 리스트를 역순으로 출력하는 함수 구성
def reverse(self):
target = self.tail
returnList = []
while target.prev is not self.head:
returnList.append(target.prev.data)
target = target.prev
return returnList
실습2
목표: 선택된 next 앞에 newNode 삽입
def insertBefore(self, next, newNode):
if next is self.head:
return False
next.prev.next = newNode
newNode.prev = next.prev
newNode.next = next
next.prev = newNode
self.nodeCount += 1
return True
실습3
목표: 값을 뽑아내는 popAfter(), popBefore(), popAt() 구현 / popAt()은 popAfter()나 popBefore()를 사용해 구현
def popAfter(self, prev):
if prev is self.tail:
return None
targetNode = prev.next
prev.next = targetNode.next
targetNode.next.prev = prev
self.nodeCount -= 1
return targetNode.data
def popBefore(self, next):
if next is self.head:
return None
targetNode = next.prev
next.prev = targetNode.prev
targetNode.prev.next = next
self.nodeCount -= 1
return targetNode.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
if self.nodeCount is 1 or pos is 1:
return self.popAfter(self.head)
else:
prevNode = self.getAt(pos-1)
return self.popAfter(prevNode)
실습4
목표: 전달받은 리스트를 뒤에 병합하는 기능 구현
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount
다른사람의 풀이를 통해 python은 , 를 통해 한번에 여러 대입이 가능함을 알았다. 상당히 직관적인 프로그래밍이 가능한 것 같다. 하지만 가독성으로는 기존 방식이 더 유리한듯 하다.
11강. 스택(Stacks)
후입선출(LIFO;
Last
In -
First
Out)로써 데이터의 입출이 동작하는 형태의 자료구조
size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함isEmpty(): 현재 스택이 비어 있는지를 판단 (size() == 0?)push(x): 데이터 원소 x 를 스택에 추가pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음
from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList
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]
class LinkedListStack:
def __init__(self):
self.data = DoublyLinkedList()
def size(self):
return self.data.getLength()
def isEmpty(self):
return self.size() == 0
def push(self, item):
node = Node(item)
self.data.insertAt(self.size() + 1, node)
def pop(self):
return self.data.popAt(self.size())
def peek(self):
return self.data.getAt(self.size()).data
실습
목표: stack 을 이용한 완성된 괄호
( ) 와 같은 형태가 존재 여부를 확인하는 기능
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 solution(expr):
match = {
')': '(',
'}': '{',
']': '['
}
S = ArrayStack()
for c in expr:
if c in '({[':
S.push(c)
elif c in match:
if S.isEmpty():
return False
else:
t = match[c]
if t != S.pop():
return False
return S.isEmpty()
12강. 스택의 응용 - 수식의 후위 표기법 (Postfix Notation)
중위표기법 (A+(B*C))-(D/E) - 연산자를 피연산자 사이에 표시, 일반적인 표기법
전위표기법 -+A*BC/DE - 연산자를 먼저, 피연산자를 나중에 표시
후위표기법 ABC*+DE/- - 피연산자를 먼저, 연산자를 나중에 표시
실습
목표: 괄호 유무에 상관없이 중위 표기를 후위 표기로 변경하는 기능 구현
에러 수정필요
def solution(S):
opStack = ArrayStack()
answer = ''
for c in S:
if c in prec:
if c is not '(' and not opStack.isEmpty() and prec[opStack.peek()] >= prec[c]:
answer += opStack.pop()
opStack.push(c)
elif c is ')':
while True:
op = opStack.pop()
if op is not '(':
break
answer += op
else:
answer += c
while not opStack.isEmpty():
op = opStack.pop()
if op is not '(':
answer += op
return answer
A-(B-C)-D*(E/F)+G 처리 요청시, ABC--DEF/*-G+ 가 아닌 ABC--DEF/*G+-로 처리된다. 이유는?
python에선 값을 while 문안에서 할당하여 바로 비교하는 연산은 불가하다고 한다. 참조
13강. 후위 표기 수식 계산
실습
목표: 후위 표기법으로 전달받은 수식을 연산하여 반환
def postfixEval(tokenList):
evalStack = ArrayStack()
for t in tokenList:
if isinstance(t,int):
evalStack.push(t)
else:
y = evalStack.pop()
x = evalStack.pop()
if t is '+':
evalStack.push(x + y)
elif t is '-':
evalStack.push(x - y)
elif t is '*':
evalStack.push(x * y)
else:
evalStack.push(x / y)
return evalStack.peek()
