数据结构--python 第四章堆栈
4.1 堆栈简介
用列表实现堆栈
用链表实现堆栈
4.2 堆栈的应用
递归算法
汉诺塔算法
老鼠走迷宫
八皇后问题(N皇后问题)
4.3 算术表达式的表示法
中序转前序，中序转后序
前序转中序，后序转中序(有括号法和堆栈法)
前序、中序、后序的求值运算
堆栈(Stack)是一组相同数据类型的组合，具有“后进先出(Last In fFirst Out),LIFO”的特性，所有的操作均在顶端进行。应用相当广泛，常用于计算机程序的运行，例如：递归调用、子程序的调用。实际生活中的应用如：大楼的电梯、货架上的商品等。
41. 堆栈的简介
堆栈是“先进后出”的数据结构，是一种抽象的数据结构类型(ADT),具有如下特性：
1）只能从堆栈的顶端存取数据，
2）数据的存取符合后进先出的原则
堆栈的5种基本运算：
| 基本运算 | 说明 |
| create | 创建一个空堆栈 |
| push | 把数据存压入堆栈顶端，并返回新堆栈 |
| pop | 从堆栈顶端弹出数据，并返回新堆栈 |
| isEmpty | 判断堆栈是否为空堆栈，若是则返回true,否则返回False |
| full | 判断堆栈是否已满，若是则返回true,否则返回False |
在pytho程序设计中，堆栈包含两种方式，分别是数组结构(在python中，是以列表List仿真数组结构)与链表结构表示堆栈。
4.1.1 用列表实现堆栈
优点：用列表实现堆栈设计非常简单
缺点：如果堆栈本身的大小是变动的，但列表的大小只能是预先规划和声明的，则列表规划太大会浪费空间，规划过小则不够用。
例子：使用数组结构来设计一个python程序，用循环来控制元素压入堆栈或弹出堆栈，并仿真堆栈的各种操作，此堆栈的最大容量是100个元素，其中必须包括压入(push)和弹出(pop)，并在最后输出堆栈内的所有元素。
# CH04-01.py
MAXSTACK=100 # 定义堆栈的最大容量
global stack
stack = [None] * MAXSTACK # 堆栈的数组声明
top = -1 # 堆栈的顶端
# 判断是否为空堆栈
def isEmpty():
if top == -1:
return True
else:
return False
# 将指定的数据压入堆栈
def push(data):
global top
global MAXSTACK
global stack
if top >= MAXSTACK-1:
print('堆栈已满,无法再加入')
else:
top += 1
stack[top] = data # 将数据压入堆栈
# 从堆栈弹出数据*/
def pop():
global top
global stack
if isEmpty():
print('堆栈是空')
else:
print('弹出的元素为: %d' % stack[top])
top = top-1
# 主程序
i = 2
count = 0
while True:
i = int(input('要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: '))
if i == -1:
break
elif i == 1:
value = int(input('请输入元素值:'))
push(value)
elif i == 0:
pop()
print('============================')
if top < 0:
print('\n 堆栈是空的')
else:
i = top
while i >= 0:
print('堆栈弹出的顺序为:%d' %(stack[i]))
count += 1
i = i-1
print
print('============================')
# 结果
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 1
请输入元素值:5
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 1
请输入元素值:6
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 1
请输入元素值:7
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 0
弹出的元素为: 7
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: -1
============================
堆栈弹出的顺序为:6
堆栈弹出的顺序为:5
============================例子：设计一个python程序，以数组仿真扑克牌洗牌以及发牌的过程。使用随机数来生成扑克牌放入堆栈，放满52张牌后开始发牌，使用堆栈功能来给4个人发牌。
# CH04-02.py
import random
global top
top = -1
k = 0
def push(stack, MAX, val):
global top
if top >= MAX-1:
print('[堆栈已经满了]')
else:
top = top+1
stack[top] = val
def pop(stack):
global top
if top < 0:
print('[堆栈已经空了]')
else:
top = top-1
return stack[top]
def shuffle(old):
result = []
while old:
p=random.randrange(0, len(old))
result.append(old[p])
old.pop(p)
return result
card = [None]*52
card_new = [None]*52
stack = [0]*52
for i in range(52):
card[i] = i+1
print('[洗牌中...请稍候!]')
card_new = shuffle(card)
i = 0
while i != 52:
push(stack, 52, card_new[i]) # 将52张牌压入堆栈
i = i+1
print('[逆时针发牌]')
print('[显示各家的牌] 东家\t 北家\t 西家\t 南家')
print('=================================')
while top >= 0:
# print(stack[top])
style = (stack[top]) % 4 # 计算牌的花色
# print('style=', style)
if style == 0: # 梅花
ascVal = 'club'
elif style == 1: # 方块
ascVal = 'diamond'
elif style == 2: # 红心
ascVal = 'heart'
elif style == 3:
ascVal='spade' # 黑桃
print('[%s%3d]\t' %(ascVal,stack[top] % 13+1), end='')
if top%4 == 0:
print()
top-=1
#结果
[洗牌中...请稍候!]
[逆时针发牌]
[显示各家的牌] 东家 北家 西家 南家
=================================
[spade 1] [heart 1] [heart 2] [club 2]
[heart 8] [spade 9] [spade 3] [spade 2]
[club 4] [spade 11] [heart 10] [diamond 3]
[spade 4] [spade 12] [heart 3] [heart 11]
[club 7] [diamond 1] [spade 8] [diamond 12]
[diamond 4] [diamond 13] [diamond 6] [club 13]
[club 12] [club 6] [spade 5] [heart 13]
[diamond 8] [spade 13] [heart 12] [heart 5]
[club 10] [spade 7] [club 11] [club 3]
[club 9] [club 5] [heart 6] [spade 10]
[heart 7] [club 1] [club 8] [diamond 10]
[diamond 11] [diamond 9] [spade 6] [heart 9]
[diamond 5] [heart 4] [diamond 2] [diamond 7] 4.1.2 用链表实现堆栈
优点：随时可以动态改变链表的长度，能有效利用内存资源，缺点：设计的算法较为复杂。
利用链表实现堆栈时，同样需要定义链表节点，包含一个next指针。
例子：设计一个python程序以链表来实现堆栈操作，并使用循环来控制元素的压入堆栈或弹出堆栈，其中必须包括压入(push)和弹出(pop)函数，并在最后输出堆栈内的元素。
# CH04-03.py
class Node: # 堆栈链结节点的声明
def __init__(self):
self.data = 0 # 堆栈数据的声明
self.next = None # 堆栈中用来指向下一个节点
top = None
# 判断堆栈是否为空，是空返回1，否则返回0
def isEmpty():
global top
if(top == None):
return 1
else:
return 0
# 将指定的数据压入堆栈
def push(data):
global top
new_add_node = Node()
new_add_node.data = data # 将传入的值指定为节点的内容
new_add_node.next = top # 将新节点指向堆栈的顶端
top = new_add_node # 新节点成为堆栈的顶端
# 从堆栈弹出数据
def pop():
global top
if isEmpty():
print('===目前为空堆栈===')
return -1
else:
ptr = top # 指向堆栈的顶端
top = top.next # 将堆栈顶端的指针指向下一个节点
temp = ptr.data # 弹出堆栈的数据
return temp # 将从堆栈弹出的数据返回给主程序
# 主程序
while True:
i = int(input('要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: '))
if i == -1:
break
elif i == 1:
value = int(input('请输入元素值:'))
push(value)
elif i == 0:
print('弹出的元素为%d' % pop())
print('============================')
while(not isEmpty()): # 将数据陆续从顶端弹出
print('堆栈弹出的顺序为:%d' % pop())
print('============================')
# 结果
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 1
请输入元素值:5
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 1
请输入元素值:6
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 1
请输入元素值:8
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 0
弹出的元素为8
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: 0
弹出的元素为6
要压入堆栈,请输入1,要弹出则输入0,停止操作则输入-1: -1
============================
堆栈弹出的顺序为:5
============================
4.2 堆栈的应用
堆栈在计算机中应用非常广泛，主要是限制了数据插入与删除的位置和方法，属于有序线性表的应用。应用举例：
1）二叉树和森林的遍历，例如：中序遍历(Inorder)、前序遍历(Preorder)等
2）计算机*处理单元(CPU)的中断处理(Interrupt Handling)
3）图形的深度优先(DFS)查找法（深度优先搜素法）
4）某些所谓的堆栈计算机(stack computer),采用空地址法指令，其指令没有操作数，大部分都通过弹出和压入两个指令来处理程序。
5）当从递归返回时，按序从堆栈顶端取出相关值，回到原来执行递归前的状态，再往下继续执行
6）算术表达式的转换和处理，例如中序法转换为后序法。
7）调用子程序和返回处理，例如在执行调用的子程序之前必须先将返回地址(下一条指令的地址)压入堆栈中，然后才开始执行调用子程序的操作，等到子程序执行完毕之后，再从堆栈中弹出返回地址。
8)编译错误处理(Complier Syntax Processing):例如当编辑程序发生错误或警告信息时，将所在的地址压入堆栈中之后，才会显示出错误相关的信息对照表。
4.2.1 应用一----递归算法
递归(Recursion)是一种特殊的算法。函数（子程序）不只是能够被其他函数调用（引用）的程序单元，在某些语言中，函数还提供调用自己的功能，这就是所谓的递归。
Q:什么时候应用递归？是不是递归只能解决少数问题？
A：事实上，任何可以用选择结构和重复结构来编写的程序代码，都可以用递归来表示和编写。
递归的定义：加入一个函数或子程序是由自身所定义或调用的，就称为递归。递归至少需要两个条件：1）可以反复执行的递归过程2）跳出执行过程的出口。
对比实验：使用for循环设计一个0！-n!的递归程序+设计一个计算n的递归程序
# CH04-04.py
# 用for循环计算 n!
sum = 1
n = int(input('请输入n='))
for i in range(0, n+1):
for j in range(i, 0, -1):
sum *= j # sum=sum*j
print('%d!=%3d' % (i, sum))
sum = 1
# 结果
请输入n=10
0!= 1
1!= 1
2!= 2
3!= 6
4!= 24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
# CH04-05.PY
# 用递归函数求 n 阶乘的值
def factorial(i):
if i == 0:
return 1
else:
product = i * factorial(i-1) # sum=n*(n-1)!所以直接调用自身
return product
n = int(input('请输入阶乘数:'))
for i in range(n+1):
print('%d !值为 %3d' % (i,factorial(i)))
# 结果
请输入阶乘数:10
0 !值为 1
1 !值为 1
2 !值为 2
3 !值为 6
4 !值为 24
5 !值为 120
6 !值为 720
7 !值为 5040
8 !值为 40320
9 !值为 362880
10 !值为 3628800根据递归调用的对象不同，可以将递归分为以下两种方式：直接递归和间接递归
直接递归：在递归函数中允许直接调用该函数本身
间接调用：在递归函数中调用其他递归函数，再从其他递归函数调用回原来的递归函数。
尾递归：程序的最后一条指令为递归调用，即每次调用后，再回到前一次调用后执行的第一条指令就是return,不需要进行任何计算工作。
4.2.2应用二----斐波那契数列
例子：设计一个计算n项斐波那契数列的递归程序。
# CH04-06.py
def fib(n): # 定义函数fib()
if n == 0:
return 0 # 如果n=0 则返回 0
elif n == 1 or n == 2:
return 1
else: # 否则返回 fib(n-1)+fib(n-2)
return (fib(n-1)+fib(n-2))
n=int(input('请输入要计算斐波拉契数列的第几项:'))
for i in range(n+1): # 计算斐波拉契数列的前n项
print('fib(%d)=%d' % (i,fib(i)))
# 结果
请输入要计算斐波拉契数列的第几项:10
fib(0)=0
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(8)=21
fib(9)=34
fib(10)=554.2.3应用三----汉诺塔问题
该问题是利用递归法与堆栈概念来解决问题的典型范例。汉诺塔问题的具体介绍可查阅文献。假设有n块木块，移动到需要的条件，最多需要移动2^n次。
汉诺塔问题很合适以递归的方式与 堆栈来解决。因为它满足递归的两大特性：1）反复执行的过程2）有停止的入口
设计一个程序，以递归的方式来实现汉诺塔算法的求解。
# CH04-07.py
def hanoi(n, p1, p2, p3):
if n == 1: # 递归出口
print('盘子从 %d 移到 %d' % (p1, p3))
else:
hanoi(n-1, p1, p3, p2)
print('盘子从 %d 移到 %d' % (p1, p3))
hanoi(n-1, p2, p1, p3)
j = int(input('请输入要移动盘子的数量：'))
hanoi(j, 1, 2, 3)
# 结果
请输入要移动盘子的数量：4
盘子从 1 移到 2
盘子从 1 移到 3
盘子从 2 移到 3
盘子从 1 移到 2
盘子从 3 移到 1
盘子从 3 移到 2
盘子从 1 移到 2
盘子从 1 移到 3
盘子从 2 移到 3
盘子从 2 移到 1
盘子从 3 移到 1
盘子从 2 移到 3
盘子从 1 移到 2
盘子从 1 移到 3
盘子从 2 移到 34.2.4应用四----老鼠走迷宫（P120）
老鼠遵守以下三个原则：
1）一次只能走一格
2）遇到墙无法往前走，退回一步找找看能否有其他的路可走
3）走过的路不会再走第二次
可以采用二维数组MAZE[row][col]，并附和一下规则：
1.MAZE[i][j]=1,表示[i][j]处有墙，无法通过
2.MAZE[i][j]=0,表示[i][j]处无墙，可以通过
3.MAZE[1][1]是入口，MAZE[m][n]是出口。
可以使用链表的方式来记录已经走过的位置，并且将走过的位置对应的数组元素内容标记为2，然后阿静这个位置放入堆栈再进行下一次的选择。
该算法时每次进行移动时所执行的操作，其主要是判断当前所在位置的上、下、左、右是否还有可以前进的方格。如果找到可以前进的方格，则将该方格的编号加入记录移动路径的堆栈中，并往该方格移动；如果四周没有可走的方格时，也就是当前所在的方格无法走出迷宫，必须退回到前一格重新检查是否有其他的可走的路径。
# CH04-08.py#=============== Program Description ===============
#程序目的： 老鼠走迷宫
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.next = None
class TraceRecord:
def __init__(self):
self.first = None
self.last = None
def isEmpty(self):
return self.first == None
def insert(self, x, y):
newNode = Node(x, y)
if self.first == None:
self.first = newNode
self.last = newNode
else:
self.last.next = newNode
self.last = newNode
def delete(self):
if self.first == None:
print('[队列已经空了]')
return
newNode = self.first
while newNode.next != self.last:
newNode = newNode.next
newNode.next = self.last.next
self.last = newNode
ExitX = 8 # 定义出口的X坐标在第8行
ExitY = 10 # 定义出口的Y坐标在第10列
# 声明迷宫数组
MAZE= [[1,1,1,1,1,1,1,1,1,1,1,1], \
[1,0,0,0,1,1,1,1,1,1,1,1], \
[1,1,1,0,1,1,0,0,0,0,1,1], \
[1,1,1,0,1,1,0,1,1,0,1,1], \
[1,1,1,0,0,0,0,1,1,0,1,1], \
[1,1,1,0,1,1,0,1,1,0,1,1], \
[1,1,1,0,1,1,0,1,1,0,1,1], \
[1,1,1,1,1,1,0,1,1,0,1,1], \
[1,1,0,0,0,0,0,0,1,0,0,1], \
[1,1,1,1,1,1,1,1,1,1,1,1]]
def chkExit(x,y,ex,ey):
if x==ex and y==ey:
if(MAZE[x-1][y]==1 or MAZE[x+1][y]==1 or MAZE[x][y-1] ==1 or MAZE[x][y+1]==2):
return 1
if(MAZE[x-1][y]==1 or MAZE[x+1][y]==1 or MAZE[x][y-1] ==2 or MAZE[x][y+1]==1):
return 1
if(MAZE[x-1][y]==1 or MAZE[x+1][y]==2 or MAZE[x][y-1] ==1 or MAZE[x][y+1]==1):
return 1
if(MAZE[x-1][y]==2 or MAZE[x+1][y]==1 or MAZE[x][y-1] ==1 or MAZE[x][y+1]==1):
return 1
return 0
# 主程序
path=TraceRecord()
x=1
y=1
print('[迷宫的路径(0标记的部分)]')
for i in range(10):
for j in range(12):
print(MAZE[i][j],end='')
print()
while x<=ExitX and y<=ExitY:
MAZE[x][y]=2
if MAZE[x-1][y]==0:
x -= 1
path.insert(x,y)
elif MAZE[x+1][y]==0:
x+=1
path.insert(x,y)
elif MAZE[x][y-1]==0:
y-=1
path.insert(x,y)
elif MAZE[x][y+1]==0:
y+=1
path.insert(x,y)
elif chkExit(x,y,ExitX,ExitY)==1:
break
else:
MAZE[x][y]=2
path.delete()
x=path.last.x
y=path.last.y
print('[老鼠走过的路径(2标记的部分)]')
for i in range(10):
for j in range(12):
print(MAZE[i][j],end='')
print()
#结果
[迷宫的路径(0标记的部分)]
111111111111
100011111111
111011000011
111011011011
111000011011
111011011011
111011011011
111111011011
110000001001
111111111111
[老鼠走过的路径(2标记的部分)]
111111111111
122211111111
111211222211
111211211211
111222211211
111211011211
111211011211
111111011211
110000001221
111111111111
4.2.5应用五----八皇后的问题（P125）
八皇后问题也是一种常见的堆栈的应用。现在要放入多个皇后到棋盘上，相互之间还不能吃到对方。后放入的皇后，放入前必须考虑所放位置的直线方向、横线方向或对角线方向是否已经被放置了旧皇后，否则就会被先放入的旧皇后吃掉。
4皇后在4x4的棋盘上，8皇后问题在8x8的棋盘上，N皇后问题就在NXN的棋盘上。
在实际过程中也会用到回朔法：如果放置新皇后的该行（列）的8个位置都没有办法放置新皇后（放入都会被之前的吃掉），此时必须从堆栈中弹出前一个皇后的位置，并在该行（列）中重新寻找另一个新的位置来放，再将该位置压入堆栈中，而这种方式就是一种回溯算法的应用。
例子：设计一个python程序，求取八皇后的解决办法。
# CH04-09.py
global queen
global number
EIGHT = 8 # 定义堆栈的最大容量
queen = [None]*8 # 存放8个皇后的行位置
number = 0 #计算总共有几组解的总数
# 决定皇后存放的位置
# 输出所需要的结果
def print_table():
global number
x=y=0
number+=1
print('')
print('八皇后问题的第%d组解\t' %number)
for x in range(EIGHT):
for y in range(EIGHT):
if x == queen[y]:
print('<q>',end='')
else:
print('<->',end='')
print('\t')
input('\n..按下任意键继续..\n')
# 测试在(row,col)上的皇后是否遭受攻击
# 若遭受攻击则返回值为1,否则返回0
def attack(row,col):
global queen
i=0
atk=0
offset_row=offset_col=0
while (atk!=1)and i<col:
offset_col=abs(i-col)
offset_row=abs(queen[i]-row)
#判断两皇后是否在同一行或在同一对角线上
if queen[i]==row or offset_row==offset_col:
atk=1
i=i+1
return atk
def decide_position(value):
global queen
i=0
while i<EIGHT:
if attack(i,value)!=1:
queen[value]=i
if value==7:
print_table()
else:
decide_position(value+1)
i=i+1
#主程序
decide_position(0)
# 结果
八皇后问题的第1组解
<q><-><-><-><-><-><-><->
<-><-><-><-><-><-><q><->
<-><-><-><-><q><-><-><->
<-><-><-><-><-><-><-><q>
<-><q><-><-><-><-><-><->
<-><-><-><q><-><-><-><->
<-><-><-><-><-><q><-><->
<-><-><q><-><-><-><-><->
..按下任意键继续..
八皇后问题的第2组解
<q><-><-><-><-><-><-><->
<-><-><-><-><-><-><q><->
<-><-><-><q><-><-><-><->
<-><-><-><-><-><q><-><->
<-><-><-><-><-><-><-><q>
<-><q><-><-><-><-><-><->
<-><-><-><-><q><-><-><->
<-><-><q><-><-><-><-><->
..按下任意键继续..
八皇后问题的第3组解
<q><-><-><-><-><-><-><->
<-><-><-><-><-><q><-><->
<-><-><-><-><-><-><-><q>
<-><-><q><-><-><-><-><->
<-><-><-><-><-><-><q><->
<-><-><-><q><-><-><-><->
<-><q><-><-><-><-><-><->
<-><-><-><-><q><-><-><->
..按下任意键继续..
八皇后问题的第4组解
<q><-><-><-><-><-><-><->
<-><-><-><-><q><-><-><->
<-><-><-><-><-><-><-><q>
<-><-><-><-><-><q><-><->
<-><-><q><-><-><-><-><->
<-><-><-><-><-><-><q><->
<-><q><-><-><-><-><-><->
<-><-><-><q><-><-><-><->
..按下任意键继续..4.3 算术表达式的表示法、
程序中这些操作数和运算符的组合就被称为‘表达式。
根据运算符在表达式中的位置，表达式可以分为以下三种表示法：
1)中序法：运算法在两个操作数中间，例如A+B
2)前序法：运算符在操作数的前面。例如：+AB
3)后序法：运算符在操作数的后面。例如：AB+
我们一般在日程生活中都使用中序法，但是中序法存在运算符优先级的问题，再加上复杂括号的困扰，计算机编译程序在处理上较为复杂。解决的办法就是将它转成后序法或前序法，因为后序法只需要一个堆栈缓存器，而前序法需要两个堆栈缓存器。
4.3.1 中序法---前序法，中序法---后序法
对于这样的转换，可采用括号转换法（人工操作）+堆栈法。其中的括号法适合人工操作，堆栈法普遍适用于计算机操作系统或程序系统中。
1.括号转换法：
括号法就是先使用括号法把中序法表达式的运算符优先级分出来，再进行运算符的移动，最后把括号拿掉就可以完成中序法往后序法或前序法的转换。
中序-前序
1）先把表达式按照运算符优先级以括号括起来
2）针对运算符，用括号内的运算符取代所有的左括号，以最近者为优先
3）将所有的右括号去掉，就得到前序法表达式的结果。
中序--后序
1）先把表达式按照运算符优先级以括号括起来
2）针对运算符，用括号内的运算符取代所有的括号，以最近者为优先
3）将所有左括号去掉，即得到后序表达式的结果
2.堆栈法
中序--前序（从右往左进行对比）
1、反转输入字符串，如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”，
2、从字符串中取出下一个字符
2.1.如果是操作数，则直接输出
2.2.如果是“)”，压入栈中
2.3.如果是运算符但不是“(”，“)”,则不断循环进行以下处理
2.3.1.如果栈为空，则此运算符进栈，结束此步骤
2.3.2.如果栈顶是“)”,则此运算符进栈，结束此步骤
2.3.2.如果此运算符与栈顶优先级相同或者更高，此运算符进栈，结束此步骤
2.3.4.否则，运算符连续出栈输出，直到满足上述三个条件之一，然后此运算符进栈
2.4、如果是“(”，则运算符连续出栈输出，直到遇见“)”为止,将“)”出栈且丢弃之
3、如果还有更多的字符串，则转到第2步
4、不在有未处理的字符串了，输出栈中剩余元素
5、再次反转字符串得到最终结果
中序--后序（从左往右进行对比）
1、当输入的是操作数时候，直接输出
2、当输入开括号时候，把它压栈
3、当输入的是闭括号时候，先判断栈是否为空，若为空，则发生错误并进行相关处理。若非空，把栈中元素依次出栈输出，直到遇到第一个开括号，若没有遇到开括号，也发生错误，进行相关处理
4、当输入是运算符op（+、- 、×、/）时候
a)循环，当（栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作：将栈顶元素出栈输出
b)把输入的运算符op压栈
5、当中序表达式的符号序列全部读入后，若栈内仍有元素，把他们依次出栈输出。若弹出的元素遇到空括号，则说明不匹配，发生错误，并进行相关处理
例子：设计一个python程序，使用堆栈法来将输入的中序法表达式转换为后序法表达式。
MAX=50
infix_q=['']*MAX
#运算符优先权的比较，若输入运算符小于堆栈中的运算符，
#则返回值为1，否则返回 0
#在中序法表达式和暂存堆栈中，运算符的优先级表，
#其优先权值为INDEX/2
def compare(stack_o, infix_o):
infix_priority=['']*9
stack_priority=['']*8
index_s=index_i=0
infix_priority[0]='q'; infix_priority[1]=')'
infix_priority[2]='+'; infix_priority[3]='-'
infix_priority[4]='*'; infix_priority[5]='/'
infix_priority[6]='^'; infix_priority[7]=' '
infix_priority[8]='('
stack_priority[0]='q'; stack_priority[1]='('
stack_priority[2]='+'; stack_priority[3]='-'
stack_priority[4]='*'; stack_priority[5]='/'
stack_priority[6]='^'; stack_priority[7]=' '
while stack_priority[index_s] != stack_o:
index_s+=1
while infix_priority[index_i] != infix_o:
index_i+=1
if int(index_s/2) >= int(index_i/2):
return 1
else:
return 0
def infix_to_postfix():
global MAX
global infix_q
rear=0; top=0; i=0
#flag=0
index = -1
stack_t=['']*MAX #以堆栈存储还不必输出的运算符
str_=str(input('请开始输入中序法表达式: '))
while i <len(str_):
index+=1
infix_q[index]=str_[i]
i+=1
infix_q[index+1]='q' #以q符号作为队列的结束符号
print('后序法表达式: ', end='')
stack_t[top]='q' #在堆栈最底端加入q为结束符号
for flag in range(index+2):
if infix_q[flag]==')': #输入为)，则输出堆栈内的运算符，直到堆栈内为(
while stack_t[top]!='(':
print('%c' %stack_t[top],end='')
top-=1
top-=1
#break
#输入为q，则将堆栈内还未输出的运算符输出
elif infix_q[flag]=='q':
while stack_t[top]!='q':
print('%c' %stack_t[top],end='')
top -=1
#break
#输入为运算符，若小于TOP在堆栈中所指向的运算符，
#则将Top所指向的运算符输出，若大于等于TOP在堆栈
#中所指的运算符，则将输入的运算符压入堆栈
elif infix_q[flag]=='(' or infix_q[flag]=='^' or \
infix_q[flag]=='*' or infix_q[flag]=='/' or \
infix_q[flag]=='+' or infix_q[flag]=='-' :
while compare(stack_t[top], infix_q[flag])==1:
print('%c' %stack_t[top], end='')
top-=1
top+=1
stack_t[top] = infix_q[flag]
#break
#输入为操作数，则直接输出
else:
print('%c' %infix_q[flag],end='')
#break
#主程序
print('------------------------------------------')
print('中序法表达式转成后序法表达式')
print('可以使用的运算符包括:^,*,+,-,/,(,)等 ')
print('------------------------------------------')
infix_to_postfix()
# 结果
------------------------------------------
中序法表达式转成后序法表达式
可以使用的运算符包括:^,*,+,-,/,(,)等
------------------------------------------
请开始输入中序法表达式: 6*5+9/2
后序法表达式: 65*92/+4.3.2 前序法---中序法，后序法---中序法
1.括号转换法：
一、前序表达式转换为中序表达式：
从右往左开始，取出一个操作符和操作符右边的两个数进行计算，并将计算的结果放过去，直到计算结束。以前序表达式“+/*23-21*3-41”为例，将其转换为中序表达式：
（1）取出“-”、4、1，计算并将结果放回得到“+/*23-21*3(4-1)”；
（2）取出“*”、3、(4-1)，计算并将结果放回得到“+/*23-21(3*(4-1))”；
（3）取出"-"、2、1，计算并将结果放回得到"+/*23(2-1)(3*(4-1))"；
（3）取出"*"、2、3，计算并将结果放回得到“+/(2*3)(2-1)(3*(4-1))”；
（4）取出"/"、(2*3)、(2-1)，计算并将结果放回得到“+((2*3)/(2-1))(3*(4-1))”；
（5）取出“+”、((2*3)/(2-1))、(3*(4-1))，计算将结果放回得到“((2*3)/(2-1))+(3*(4-1))”，计算结束,显然计算结果为15；
二、后序表达式转换为中序表达式：
从左向右开始，取出一个操作符和操作符左边的两个数进行计算，并将计算的结果放过去，直到计算结束，以后序表达式“ab+cde+**”为例，将其转换为中序表达式：
（1）取出“+”、a、b，计算并将结果放回得到“(a+b)cde+**”；
（2）取出"+"、d、e，计算并将结果放回得到"(a+b)c(d+e)**"；
（3）取出“*”、c、(d+e)，计算并将结果放回得到“(a+b)(c*(d+e))*”；
（4）取出"*"、(a+b)、(c*(d+e))，计算并将结果放回得到"(a+b)*(c*(d+e))"；显然，计算结束
2.堆栈法
1）若要将前序表达式转换为中序表达式，从右往左读进表达式的每一个token；若要将后序表达式转换成中序表达式，则读取的方向是从左到右。
2）辨别读入的字符，如是操作数，则直接压入堆栈中，
3）辨别读入的字符，如果为运算符，则从堆栈中弹出两个字符，组合成一个基本的中序表达式（操作数）（运算符）（操作数），在把结果压入堆栈中。
4）在转换过程中，前序和后序的组合方式是不同的，前序表达式的顺序是（操作数2）（运算符）（操作数1），而后序表达式则是（操作数1）（运算符）（操作数2）
即前序转中序：<op2><运算符><op1>
后序转中序：<op1><运算符><op2>
总之：
中-前：添括号，最近邻原则，用运算符代替"("；堆栈法采用从右到左进行读取
中-后：添括号，最近邻原则，用运算符代替“）”；堆栈法采用从左往右
前-中：从右往左读取，<op2><运算符><op1>
后-中：从左往右读取，<op1><运算符><op2>
到目前为止，介绍了中-前和中-后的括号法和堆栈法。前-中和后-中的括号法和堆栈法。
4.3.3 中序表达式的求值运算
1）建立两个堆栈，分别存放运算符和操作数
2）读取运算符时，必须先比较堆栈内的运算符优先级，若堆栈内运算符的优先级较高，则先计算堆栈内运算符的值
3）计算时，弹出一个运算符和两个操作数来进行运算，运算结果直接存放回操作数堆栈中。
4）当表达式处理完成后，一步一步的清除运算符堆栈，指导堆栈清空为止
5）弹出操作数堆栈中的值就是计算结果。
4.3.4 前序法表达式的求值运算
使用中序法表达式来求值，必须考虑到运算符的优先级，所以要建立两个堆栈，分别存放运算符和操作数。如果使用前序法表达式来求值，好处是不需要考虑括号和优先级问题，可以直接使用一个堆栈来处理表达式，而不需要把操作数和运算符分开处理。
4.3.5 后序表达式的求值运算
后序法表达式具有和前序表达式类似的好处，没有优先级的问题。后序表达式可以直接在计算机上进行运算，而不需要先全数压入堆栈后再读回运算。在后序法表达式中，它使用循环直接读取表达式，如果遇到运算符，就从堆栈中弹出操作数进行运算。