1.栈
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
括号匹配
tips
def matches(open, close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
从中序到后序的转换
- 创建用于保护运算符的空栈opstack,以及一个用于保存结果的空列表
- 将中序表达式转换为列表
- 从左往右扫描这个标记列表
- 如果标记是操作数,将其添加到结果列表的末尾
- 如果标记是左括号,将其压入opstack栈中
- 如果标记是右括号,反复从opstack栈中移除元素,直到移除对应的左括号。将从栈中取出的每一个运算符都添加到结果列表的末尾
- 如果标记是运算符,将其压入opstack栈中。但是,在这之前,需要先从栈中取出优先级更高或相同的运算符,并将它们添加到结果列表的末尾
- 当处理完输入表达式以后,检查opstack。将其中所有残留的运算符全部添加到结果列表的末尾
tips
import string
if token in string.ascii_uppercase: ##判断是否为字母
2.队列
2.1 单向队列
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
return self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
2.2 双端队列
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
return self.items.pop()
def removeRear(self, item):
return self.items.pop(0)
def size(self):
return len(self.items)
3.无序列表
列表是元素的集合,其中的每个元素都有一个相对于其他元素的位置
3.1 Node类
每个节点保存两个信息,数据变量与指向下一个节点的引用
class Node:
def __init__(self, initdata=0):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
3.2 UnorderedList类
#UnorderedList类
class UnderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head is None
#头插法
def add(self, item):
newnode = Node(item)
newnode.setNext(self.head)
self.head = newnode
def length(self):
current = self.head
count = 0
while current:
count = count + 1
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self, item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
4.有序列表
#有序列表
class OrederedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head is None
def length(self):
current = self.head
count = 0
while current:
count = count + 1
return count
def search(self, item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getNext().getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self, item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(previous)
previous.setNext(temp)