1.名词解释
? ? ? ? 1.1?中缀表达式
? ? ? ? ? ? ? ? ? ? ? ? 普通表达式,即操作符位于操作数的中间。如''2+3*5'',''(2+3)*5''。这种表达式的特点是根据运算符的优先级不同，计算顺序不同。可以通过添加括号来改变计算的顺序，这种表达式人类理解起来没什么问题，但计算机识别起来就有点困难。
? ? ? ? 1.2 全括号表达式
? ? ? ? ? ? ? ? ? ? ? ? 为了方便计算机识别表达式，可以将中缀通过添加括号的方法转化为全括号表达式，即每一次运算都添加一对括号来保证计算的优先级。如"(2+(3*5))","((2+3)*5)",全括号表达式解决了计算机识别的问题。但是又出现了新的问题，括号太多，增加了处理负担。显得不够优雅，发现了问题，自然就会诞生解决问题的牛人，1929年波兰的逻辑学家卢卡西维兹(Jan Lucasiewicz)提出了将运算符放在运算项前面的逻辑表达式，又称“波兰表达式”。优雅地地解决了这个问题
? ? ? ? 1.3?前缀表达式(波兰式)
? ? ? ? ? ? ? ? ? ? ? ? 波兰式表达式，就是将运算符放在两个运算数的前面的表达式，如"+ 2 * 3 5","*+ 2 3 5"。可以发现波兰式完全消灭了括号，而且还能保证运算顺序和对应的中缀表达式相同。这里也解释一下波兰式的运算规则，（后续将利用这个规则进行波兰式的求值。）如果一个操作符的后面是两个操作数，则直接运算，如果是一个操作数+一个操作符，说明要先运算第二个操作符。再将结果与第一个数进行运算得到结果 。
eg："+ 2 * 3 5"
第一个操作符 “+” ，接下来是操作数 2，
? ? ? ? 接下来又是操作符’* ，说明要先运算”*“
? ? ? ? ? ? ? ? 接下来是两个操作数 3 和 5 ，作乘法的结果是15
? ? ? ? 将结果15作为’+“的第二个操作数
得到2+15 =17
? ? ? ? 1.4?后缀表达式(逆波兰式)
? ? ? ? ? ? ? ? ? ? ? ? 所谓逆波兰式，就是将运算符放在两个运算数的后面的表达式，如"2 3 5 * +","2 3 +5*"。
2.如何把中缀表达式转化为波兰式
????????2.1 先转化为全括号表达式
???????????????如："2+3*5''
????????????????得到全括号表达式："（2+（3*5））''
????????????????观察全括号表达式,得到转化的方法：将运算符替换掉对应的左括号，同时删除右括号
? ? ? ? ?2.2 利用栈的后进先出的特性来转化
2.2.1 先用python来定义一个栈的抽象数据类型
代码如下：
class Stack:
def __init__(self):
self.items = []
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
def peek(self):
return self.items[-1]
def __str__(self):
return '{}←'.format(self.items)? ? ?2.2.2接下来定义一个函数来处理输入数据。将中缀表达式的字符串转成一个列表，方便后续处理
def inputProcess(inputString):
'''将输入的字符串转化为包含操作数和操作符的列表'''
resList = []
tmp = '' # 用于保存多位的数字时的中间结果
for ele in inputString:
if ele.isdigit() or ele == '.': # 能处理小数点的情况
tmp += str(ele)
else:
if tmp != '':
resList.append(tmp)
tmp = ''
resList.append(ele)
if tmp != '':
resList.append(tmp)
return resList? ? 这里有一个问题，将一个字符串变为列表，可能有更加简单的方法，如? ? ? ? ? ? ?
# 字符串转列表
lis = list('(1+2+3)*9')
print(lis)
>>>['(', '1', '+', '2', '+', '3', ')', '*', '9'] # 结果正确
# 但是不能处理如下情况
lis1 = list('(10+28+3)*9')
print(lis1)
>>>['(', '1', '0', '+', '2', '8', '+', '3', ')', '*', '9'] # 10,28 被分割成了两个元素? ? ?2.2.3? ? 编写转化的主函数
def inToPreExp(epxString):
expList = inputProcess(epxString)
s = Stack()
optPriorityDict = {')':0,'+':1,'-':1,'*':2,'/':2} # 操作符优先级字典
res = [] # 保存结果
for ele in expList[::-1]: # 逆序扫描列表
if ele.isdigit(): # 1数字直接添加进结果字符串
res.insert(0,ele) # 为保证数字顺序,所有从左边插入进结果列表
elif ele == ')': # 2.右括号压栈
s.push(ele)
elif ele =='(': # 3.左括号,连续出栈直到右括号,并追加到结果字符串
top = s.pop()
while top != ')':
res.insert(0,top)
top = s.pop()
elif ele in '+-*/': # 4 操作符和栈顶元素比较优先级
while (not s.isEmpty() and \
optPriorityDict[s.peek()] >= optPriorityDict[ele]): # 当前栈顶元素的优先级大于等于扫描到的运算符
res.insert(0, s.pop()) # 出栈并插入结果列表
s.push(ele) # 入栈
while not s.isEmpty():
res.insert(0,s.pop())
return res算法：
1.创建优先级字典,初始化一个空栈,用于保存操作符,一个空列表用于保存结果,
逆序扫描列表
2.如果遇到数字，直接插入进结果列表的最左边
3.如果是“）”：
? ? ? ? 入栈
4.如果遇到"(":
? ? ? ? 持续出栈,并插入到结果列表,直到遇到")"
5.如果是"+-*/":
? ? ? ? 如果栈顶元素的优先级比当前操作符大,则连续出栈
? ? ? ? 当前操作符入栈
6.扫描完成以后,如果栈不为空,则一次出栈.插入到结果列表
以下是一些测试
print(inToPreExp('(2+3)*5'))
print(inToPreExp('2+3*5'))
print(inToPreExp('(12-5)*(23+8)'))
print(inToPreExp('2+3*7/20-(2+3)'))
结果:
['*', '+', '2', '3', '5']
['+', '2', '*', '3', '5']
['*', '-', '12', '5', '+', '23', '8']
['+', '2', '-', '*', '3', '/', '7', '20', '+', '2', '3']3.波兰式求值
直接上代码:
def evalPreExp(postExpList):
# 前缀表达式求值
s = Stack()
for ele in postExpList[::-1]:
if ele.isdigit():
s.push(ele)
else:
op1 = s.pop()
op2 = s.pop()
res = toMath(ele,int(op1),int(op2))
s.push(res)
return s.pop()
def toMath(op,op1,op2):
# 根据不同的运算符做四则运算
if op == '+':
return op1 + op2
elif op == '-':
return op1 - op2
elif op == '*':
return op1 * op2
elif op == '/':
return op1 / op2
print(evalPreExp(['*', '-', '12', '5', '+', '23', '8'])) # >>> 结果:217总结:
波兰式和逆波兰式因其优雅简洁而闻名
大部分教程都是中缀到后缀的转化
尝试了一下中缀到前缀的转化
需要注意的几个重点:
1.优先级字典中设置右括号为最低优先级,? ?中缀转后缀时,左括号的优先级最低
2.扫描列表的时候?逆序
3.因为时逆序扫描,为保证操作数的位置不变,所以插入到结果列表的时候使用insert(0,ele)的方法从左边插入
参考书籍:
Bradley N. Miller, David L. Ranum <<Introduction to Data Structures and Algorithms in Python>>
35岁开始学Python ,?也不知道为了啥 ?