波兰表达式 #

1. 波兰表达式的介绍
2. 波兰表达式的算法分析
3. 波兰表达式的代码实现

波兰表达式的介绍及函数的定义 #

波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式 2+3 的波兰表示法为 + 2 3 (把运算符放在后面的称为逆波兰表达式)。
波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，十分适用计算机内部计算。例如* + 11.0 12.0 + 24.0 35.04的波兰表达式值为：(11.0+12.0)*(24.0+35.04)。波兰表达式的定义可总结如下:
1)一个数是一个波兰表达式，值为该数
2)” 运算符   波兰表达式   波兰表达式 “是波兰表达式，值为两个波兰表达式的值运算的结果

波兰表达式的算法分析 #

如果输入一段字符串代表波兰表达式，每个字符用空格隔开，该如何求解波兰表达式代表的结果值呢？因为波兰表达式本身就是一个递归的定义，我们不妨定义函数 f( l ),参数l是波兰表达式的字符列表，功能是返回波兰表达式的值。
1）波兰表达式定义的第一条即是该函数的出口，即是如果l[0]为数字的话，它本身就是波兰表达式的值。
2）波兰表达式的第二条即是波兰表达式问题的拆解，即是一个大的波兰表达式可以拆解成一个运算符号与两个波兰表达式

波兰表达式的代码实现 #

str=input()#输入波兰表达式，中间使用空格隔开
liststr=str.split()
def f(l):
    i=l.pop(0) #每次调用将l的首个字符弹出
    if(i=="*"):return f(l)*f(l) #波兰表达式问题的拆解
    elif(i=="/"):return f(l)/f(l)
    elif(i == "+"):return f(l)+f(l)
    elif(i == "-"):return f(l)-f(l)
    else:return float(i) #递归的出口 如果该字符是数字，返回该数字 
print(f(liststr))#打印结果

小结 #

• 根据波兰表达式的递归算法，理解递归算法的三要素
• 掌握波兰表达式的递归算法

习题 #

1. 尝试不用递归求解波兰表达式表示的值
2. 将波兰表达式倒着读就是逆波兰表达式，请用递归的方法求解逆波兰表达式的值