Python实现数据结构系列(3)

接着上一节的python实现基本数据结构的内容,今天我们继续来实现中缀表达式到前缀表达式的实现过程。

中缀到前缀示例:

( 4 + 2 ) * ( 3 + 6 ) => * + 4 2 + 3 6

(3 /4 + 2) - 5 => - + / 3 4 2 5

(3 + 4/2) - 5 => - + 3 / 4 2 5

如果将表达式画成树形结构,则前缀、中缀、后缀分别是树的先序、中序、后序遍历。

-----------------*------------------

------------/-----------\-----------

--------+----------------+---------

------/----\------------/-----\------

----4-------2---------3-------6----

思路1(栈):

1. 从右向左读

2. 遇到数字添加到输出流头部,遇到符号则按优先级判断入栈:

1)低入高出

2)右括号,出栈直到遇到左括号

思路2(补全括号):

1. 中缀:a+b*c-(d+e)

2. 按优先级补括号:((a + (b*c)) - (d+e))

3. 移动操作符到括号前:-(+(a*(bc))+(de))

4. 去括号:- + a * b c + d e

PS:

后缀与此类似,只是将操作符移植相应括号后方。

思路3(树):

1. 中缀转成树结构(按操作符优先级)

2. 先序遍历树结构

现在就思路1(栈)用栈来实现中缀转前缀表达式的实现过程:

def infixToPrefix(infixExp):

'''

根中缀转后缀不同,表达式反序从右到左顺序读取每一个字符

如果遇到操作数,直接将操作数放入到prefixList 中

如果遇到操作符,如果符号栈为空,直接放入符号栈中,如果符号栈不为空,则判断当前栈顶元素

如果当前栈顶元素为右括号‘)’,直接将操作符放入符号栈中

如果当前栈顶元素的优先级大于操作符的优先级,则将栈顶元素移除,再次和判断移除后栈的栈顶元素比较优先级大小,直到当前栈顶元素小于或等于操作数优先级,将操作符放入符号栈中

如果遇到右括号,直接将右括号放入符号栈中

如果遇到左括号,将右括号到左括号之间的全部符号移出到prefix 中(记得左括号不要入栈,并且在最后将右括号从栈中删除)

重复1-4,直到最后一个字符被读入。

判断当前栈是否为空,如果不为空,将栈中的元素依次移出到prefix 中

翻转字符串

exp: 1 + 2 * 3 + ( 4 * 5 + 6 ) * 7 转换成 ++1*23+*4567

'''

tokenList = infixExp.split()

print(tokenList)

tokenList.reverse()

print(tokenList)

prec = {}

prec["*"] = 3

prec["/"] = 3

prec["+"] = 2

prec["-"] = 2

prec["("] = 1

prec[")"] = 1

opStack = Stack()

prefixList = []

for token in tokenList:

if token:

if token.isdigit() or token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":

prefixList.append(token)

else:

if opStack.isEmpty():

opStack.push(token)

elif token == ')':

opStack.push(token)

elif token == '(':

topToken = opStack.peek()

while (topToken and topToken != ')'):

item = opStack.pop()

if topToken != ')':

prefixList.append(item)

topToken = opStack.peek()

if topToken == ')':

opStack.pop()

else:

topToken = opStack.peek()

while topToken and prec[topToken] > prec[token]:

item = opStack.pop()

prefixList.append(item)

topToken = opStack.peek()

#push token to stack

opStack.push(token)

print(opStack)

print(prefixList)

print(token+'****'*6)

while not opStack.isEmpty():

prefixList.append(opStack.pop())

prefixList.reverse()

return ' '.join(prefixList)

接下来学习双端队列Deque.

1.什么是Deque

deque(也称为双端队列)是与队列类似的项的有序集合。它有两个端部,首部和尾部,并且项在集合中保持不变。deque 不同的地方是添加和删除项是非限制性的。可以在前面或后面添加新项。同样,可以从任一端移除现有项。在某种意义上,这种混合线性结构提供了单个数据结构中的栈和队列的所有能力。 Figure 1 展示了一个 Python 数据对象的 deque 。

要注意,即使 deque 可以拥有栈和队列的许多特性,它不需要由那些数据结构强制的 LIFO 和 FIFO 排序。这取决于你如何持续添加和删除操作。

Deque抽象数据类型

deque 抽象数据类型由以下结构和操作定义。如上所述,deque 被构造为项的有序集合,其中项从首部或尾部的任一端添加和移除。下面给出了 deque 操作。

Deque() 创建一个空的新 deque。它不需要参数,并返回空的 deque。

addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。

addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。

removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。

removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。

isEmpty() 测试 deque 是否为空。它不需要参数,并返回布尔值。

size() 返回 deque 中的项数。它不需要参数,并返回一个整数。

例如,我们假设 d 是已经创建并且当前为空的 deque,则 Table 1 展示了一系列 deque 操作的结果。注意,首部的内容列在右边。在将 item 移入和移出时,跟踪前面和后面是非常重要的,因为可能会有点混乱。

Python实现Deque

正如我们在前面的部分中所做的,我们将为抽象数据类型 deque 的实现创建一个新类。同样,Python 列表将提供一组非常好的方法来构建 deque 的细节。我们的实现(Listing 1)将假定 deque 的尾部在列表中的位置为 0。

'''

Created on 2018年5月10日

@author: water

'''

class Deque(object):

def __init__(self):

self.items = []

def isEmpty(self):

return self.item == []

def addFront(self, item):

self.items.append(item)

def addRear(self, item):

self.items.insert(0, item)

def removeFront(self):

try:

return self.items.pop()

except IndexError:

return None

def removeRear(self):

try:

return self.items.pop(0)

except IndexError:

return None

def size(self):

return len(self.items)

注:在 removeFront 中,我们使用 pop 方法从列表中删除最后一个元素。 但是,在removeRear中,pop(0)方法必须删除列表的第一个元素。同样,我们需要在 addRear 中使用insert方法,因为 append 方法在列表的末尾添加一个新元素。

你可以看到许多与栈和队列中描述的 Python 代码相似之处。你也可能观察到,在这个实现中,从前面添加和删除项是 O(1),而从后面添加和删除是 O(n)。 考虑到添加和删除项是出现的常见操作,这是可预期的。 同样,重要的是要确定我们知道在实现中前后都分配在哪里。

Deque使用实例:回文检查

使用 deque 数据结构可以容易地解决经典回文问题。回文是一个字符串,读取首尾相同的字符,例如,。 我们想构造一个算法输入一个字符串,并检查它是否是一个回文。

该问题的解决方案将使用 deque 来存储字符串的字符。我们从左到右处理字符串,并将每个字符添加到 deque 的尾部。在这一点上,deque 像一个普通的队列。然而,我们现在可以利用 deque 的双重功能。 deque 的首部保存字符串的第一个字符,deque 的尾部保存最后一个字符(见 Figure 2)

Figure 2

我们可以直接删除并比较首尾字符,只有当它们匹配时才继续。如果可以持续匹配首尾字符,我们最终要么用完字符,要么留出大小为 1 的deque,取决于原始字符串的长度是偶数还是奇数。在任一情况下,字符串都是回文。 回文检查的完整功能在如下代码中。

def palchecker(palString):

'''回文检测'''

chardeque = Deque()

for i in palString:

chardeque.addRear(i)

equal = True

while equal and chardeque.size() > 1:

first = chardeque.removeFront()

last = chardeque.removeRear()

if first != last:

equal = False

return equal

今天的python数据结构Deque就到这里,下一节会介绍如何用链表实现LIST(列表)的python代码。谢谢。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180606G13MNT00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励