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代码。谢谢。