本人手写或借阅资料，仅供参考，有错误欢迎指正。
import random
from pythonds.basic import Stack, Queue, Deque#中序表达式到后序表达式的转换
#3.1 修改从中序到后序的转换算法，使其能处理异常情况。
def infixToPostfix(indixexpr):
prec = {'*':3, '/':3, '+':2, '-':2, '(':1}
opStack = Stack()
tokenList = indixexpr.split()
postfixlist = []
try:
for token in tokenList:
if isnumber(token):
postfixlist.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
toptoken = opStack.pop()
while toptoken != '(':
postfixlist.append(toptoken)
toptoken = opStack.pop()
else:
while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
postfixlist.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixlist.append(opStack.pop())
return " ".join(postfixlist)
except:
return "中序表达式格式错误"#计算后序表达式
#3.2 修改计算后序表达式的算法，使其能处理异常情况。
def postfixEval(postfixExpr):
opStack = Stack()
tokenList = postfixExpr.split()
try:
for token in tokenList:
if isnumber(token):
opStack.push(int(token))
else:
operatenum1 = opStack.pop()
operatenum2 = opStack.pop()
res = domath(token, operatenum1, operatenum2)
opStack.push(res)
return opStack.pop()
except:
return "后序表达式格式错误"#3.3 结合从中序到后序的转换算法以及计算后序表达式的算法，实现直接的中序计算。在计
#算时，应该使用两个栈从左往右处理中序表达式标记。一个栈用于保存运算符，另一个
#用于保存 *** 作数。
def infixEval(infixExpr):
opStack = Stack()
signStack = Stack()
tokenList = infixExpr.split()
for token in tokenList:
if token in ['+', '-', '*', '/', '(', ')']:
if token == ')':
while signStack.peek() != '(':
operatenum2 = opStack.pop()
signlabel = signStack.pop()
operatenum1 = opStack.pop()
res = domath(signlabel, operatenum1, operatenum2)
opStack.push(res)
signStack.pop()
else:
signStack.push(token)
else:
opStack.push(int(token))
while not signStack.isEmpty():
operatenum2 = opStack.pop()
signlabel = signStack.pop()
operatenum1 = opStack.pop()
res = domath(signlabel, operatenum1, operatenum2)
opStack.push(res)
return opStack.pop()
def domath(operation, num1, num2):
if operation == '+':
return num1 + num2
elif operation == '-':
return num1 - num2
elif operation == '*':
return num1 * num2
else:
return num1 / num2
def isnumber(s):
try:
float(s)
return True
except ValueError:
return False
def infixToPostfixtest():
s = "( 11 + 2 ) * 3"
print(infixToPostfix(s))
print(postfixEval(infixToPostfix(s)))
def infixEvaltest():
print(infixEval("( ( ( 1 + 2 ) * 3 ) - ( 4 + 5 + 6 - 7 ) ) * 8"))
#3.5 使用列表实现队列抽象数据类型，将列表的后端作为队列的尾部。
class Myqueue():
def __init__(self):
self.data = []
def enqueue(self, v):
self.data.insert(0, v)
def dequeue(self):
return self.data.pop()#队列，约瑟夫环问题（传土豆）
#3.9 修改传土豆模拟程序，允许随机计数，从而使每一轮的结果都不可预测
def hotpotato(namelist):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:
num = random.randrange(simqueue.size()*2)
for i in range(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
def hotpotatotest():
print(hotpotato(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']))#3.10 基数排序器：
def Cardinalsort(l):
res = []
qlist = []
masterqueue = Queue()
maxlen = 0
length = len(l)
for i in range(10):
qlist.append(Queue())
for num in l:
maxlen = max(maxlen, len(str(num)))
masterqueue.enqueue(num)
for i in range(1, maxlen + 1):
for _ in range(length):
cur = masterqueue.dequeue()
if len(str(cur)) < i:
masterqueue.enqueue(cur)
else:
slavenum = str(cur)[-i]
qlist[int(slavenum)].enqueue(cur)
for j in range(10):
while not qlist[j].isEmpty():
masterqueue.enqueue(qlist[j].dequeue())
while not masterqueue.isEmpty():
res.append(masterqueue.dequeue())
return res
def Cardinalsorttest():
ml = [666, 1, 24, 3, 67, 9, 45]
print(Cardinalsort(ml))#3.11 HTML 中也存在括号匹配问题。标签有开始和结束两种形式，并
#且需要互相匹配才能正确描述网页内容
def htmlchecker():
htstack = Stack()
isvalid = True
idx = 0
tmp = ''
with open("E:\Ace_exercise\Cpython_exercise\homework\homework3_html.html") as htmlobj:
htmlcontents = htmlobj.read()
try:
while idx < len(htmlcontents) and isvalid:
if htmlcontents[idx] == '<' and idx + 1 < len(htmlcontents) and htmlcontents[idx + 1] != '/':
idx += 1
while htmlcontents[idx] != '>':
tmp += htmlcontents[idx]
idx += 1
htstack.push(tmp)
tmp = ''
elif htmlcontents[idx] == '<' and idx + 1 < len(htmlcontents) and htmlcontents[idx + 1] == '/':
idx += 2
while htmlcontents[idx] != '>':
tmp += htmlcontents[idx]
idx += 1
if htstack.pop() != tmp:
isvalid = False
tmp = ''
else:
idx += 1
except:
return False
if not isvalid or not htstack.isEmpty():
return False
return True
def htmlcheckertest():
print(htmlchecker())
#双端队列，回文检测器
#3.12 扩展代码清单3-15 中的回文检测器，使其可以处理包含空格的回文。如果忽略其中的
#空格，那么I PREFER PI 就是回文。
def palchecker(aString):
charDeque = Deque()
for ch in aString:
if ch == ' ':
continue
charDeque.addFront(ch)
stillEqual = True
while charDeque.size() > 1 and stillEqual:
if charDeque.removeFront() != charDeque.removeRear():
stillEqual = False
return stillEqual
def palcheckertest():
print(palchecker('I PREFER PI'))#3.13 本章通过计算列表中节点的个数来实现length 方法。另一种做法是将节点个数作为额
#外的信息保存在列表头中。请修改UnorderedList 类的实现，使其包含节点个数信息，
#并且重新实现length 方法。
#3.14 实现remove 方法，使其能正确处理待移除元素不在列表中的情况
#3.17 实现__str__方法，使列表按照Python 的方式来显示（使用方括号）
#3.18 实现无序列表抽象数据类型剩余的方法：append、index、pop 和insert。
#3.19 实现UnorderedList 类的slice 方法。
class Node():
def __init__(self, initdata):
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
class UnorderedList():
def __init__(self):
self.head = None
self.mlength = 0
def __str__(self):
res = ""
cur = self.head
while cur:
res += str(cur.getData())
cur = cur.getNext()
return '[' + res + ']'
def append(self, other):
cur = self.head
while cur.getNext():
cur = cur.getNext()
cur.setNext(other.head)
def index(self, v):
idx = 0
cur = self.head
while cur and cur.getData() != v:
cur = cur.getNext()
idx += 1
if not cur:
return -1
return idx
def pop(self):
cur = self.head
if not self.mlength:
print ("空列表, 无法d出")
return
pre = None
while cur.getNext():
pre = cur
cur = cur.getNext()
if not pre:
self.head = None
self.mlength -= 1
return cur.getData()
else:
pre.setNext(None)
self.mlength -= 1
return cur.getData()
def insert(self, idx, v):
if idx < 0:
return "索引错误"
if idx == 0:
self.add(v)
return
cur = self.head
idx -= 1
while cur and idx:
cur = cur.getNext()
idx -= 1
newNode = Node(v)
nex = cur.getNext()
cur.setNext(newNode)
newNode.setNext(nex)
def slice(self, start, end):
if self.mlength < end - start:
return "越界"
tmp = str(self)
return '[' + tmp[start + 1: end + 1] + ']'
def isEmpty(self):
return self.head == None
def add(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
self.mlength += 1
def length1(self):
cur = self.head
count = 0
while cur != None:
count += 1
cur = cur.getNext()
return count
def length2(self):
return self.mlength
def search(self, item):
cur = self.head
found = False
while cur != None and not found:
if cur.getData() == item:
found = True
else:
cur = cur.getNext()
return found
def remove(self, item):
cur = self.head
pre = None
found = False
while cur and not found:
if cur.getData() == item:
found = True
else:
pre = cur
cur = cur.getNext()
if not cur:
print("无此元素")
return
if not pre:
self.head = cur.getNext
else:
pre.setNext(cur.getNext())
self.mlength -= 1
def unorderedlisttest1():
ul = UnorderedList()
ur = UnorderedList()
print(ul.pop())
ul.add(5)
print(ul.length2())
ur.add(6)
ul.add(7)
ul.add(8)
print(ul.length2())
ul.remove(0)
print(ul.length2())
ul.remove(5)
print(ul.length2())
print(ul.length1())
print(str(ul))
while not ul.isEmpty():
print(ul.pop())
ul.add(7)
ul.add(8)
print(str(ul))
print(str(ur))
ul.append(ur)
print(str(ul))
print(ul.index(6))
ul.insert(0,4)
ul.insert(2,5)
print(str(ul))
print(ul.slice(0,2))#3.20 实现有序列表抽象数据类型剩余的方法
class OrderedList():
def __init__(self):
self.head = None
def __str__(self):
res = ""
cur = self.head
while cur:
res += str(cur.getData())
cur = cur.getNext()
return '[' + res + ']'
def isEmpty(self):
return self.head == None
def length(self):
cur = self.head
count = 0
while cur:
count += 1
cur = cur.getNext()
return count
def remove(self, v):
cur = self.head
pre = None
found = False
while cur and not found:
if cur.getData() == v:
found = True
else:
pre = cur
cur = cur.getNext()
if not cur:
print("无此元素")
return
if not pre:
self.head = cur.getNext
else:
pre.setNext(cur.getNext())
self.mlength -= 1
def search(self, v):
cur = self.head
found = False
stop = False
while cur and not found and not stop:
if cur.getData() == v:
found = True
else:
if cur.getData() > v:
stop = True
else:
cur = cur.getNext()
return found
def add(self, v):
cur = self.head
pre = None
stop = False
while cur and not stop:
if cur.getData() > v:
stop = True
else:
pre = cur
cur = cur.getNext()
temp = Node(v)
if pre == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(cur)
pre.setNext(temp)#3.21 思考有序列表和无序列表的关系。能否利用继承关系来构建更高效的实现？试着实现这
#个继承结构。
class OrderedFromUnorederedlist(UnorderedList):
def __init__(self):
super().__init__()
def search(self, v):
cur = self.head
found = False
stop = False
while cur and not found and not stop:
if cur.getData() == v:
found = True
else:
if cur.getData() > v:
stop = True
else:
cur = cur.getNext()
return found
def add(self, v):
cur = self.head
pre = None
stop = False
while cur and not stop:
if cur.getData() > v:
stop = True
else:
pre = cur
cur = cur.getNext()
temp = Node(v)
if pre == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(cur)
pre.setNext(temp)
def OrderedFromUnorederedlisttest():
ol = OrderedFromUnorederedlist()
ol.add(67)
ol.add(35)
ol.add(97)
ol.add(22)
print(str(ol))
print(ol.index(97))#3.22 使用链表实现栈
class UnorderedListStack(UnorderedList):
def __init__(self):
super().__init__()
def stackpush(self, v):
self.add(v)
def stackpop(self):
if self.mlength <= 0:
return False
self.mlength -= 1
cur = self.head
if cur.getNext():
self.head = cur.getNext()
return cur.getData()
def UnorderedListStacktest():
us = UnorderedListStack()
us.stackpush(5)
us.stackpush(6)
print(us.stackpop())
print(us.stackpop())
print(us.stackpop())#3.27 请用Python 实现双向链表。
class DoubleNode(Node):
def __init__(self, initdata):
super().__init__(initdata)
self.pre = None
def getpre(self):
return self.pre
def setpre(self, newpre):
self.pre = newpre
class DoubleList(UnorderedList):
def __init__(self):
super().__init__()
def add(self, item):
temp = DoubleNode(item)
temp.setNext(self.head)
if self.head:
self.head.setpre(temp)
self.head = temp
def remove(self, v):
cur = self.head
pre = None
found = False
while not found:
if cur.getData() == v:
found = True
else:
pre = cur
cur = cur.getNext()
if not pre:
self.head = cur.getNext()
cur.getNext().setpre(None)
else:
pre.setNext(cur.getNext())
pre.getNext().setpre(pre)
def DoubleListtest():
dl = DoubleList()
dl.add(4)
dl.add(3)
dl.add(2)
dl.add(1)
print(str(dl))
dl.remove(3)
print(str(dl))欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）