注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为6分钟。
这一节要讲的是，如何使用Python实现后缀表达式求值的算法，当然要用到栈这一基本结构。
后缀表达式求值介绍
后缀表达式求值和上一节的“中缀表达式转换为后缀表达式”有所不同，在对后缀表达式进行从左至右的扫描过程当中，由于操作符在操作数的后面，所以要找一个容器把操作数暂时存放起来。
等碰到操作符的时候，再将暂时存放的两个操作数从那个容器提取出来并进行实际计算。
这个容器显然需要具备LIFO（后进先出）的特性：操作符只作用于距离它最近的两个操作数——也就是最后入栈的两个操作数，会被最先计算。
很明显，栈能很好地扮演这个容器，实现其所需功能。
一个具体例子说明后缀表达式求值的算法
例如，求"4 5 6 * +"这个后缀表达式的值。具体算法流程如下：
- 程序从左至右扫描，先扫描到4、5两个操作数，并把它们暂时存放到一个空栈里。
- 继续从左至右扫描，又碰到操作数6，不知道如何计算，继续存入栈顶。
- 继续扫描，遇到了“*”。距离“*”最近的是此前陆续存入栈的6和5（6在栈顶，5紧挨着6），所以我们知道操作数5和6的操作符是“*”，所以有这一步计算：5 * 6。这里要注意的是，先弹出来的操作数6（也就是栈顶的那个操作数）是右操作数，而后弹出来的操作数5则是左操作数，这种顺序对于减法和乘法很重要，因为顺序不同，计算结果是不同的。
- 继续上一步的5 * 6，计算得到30这个新的操作数。30这个操作数继续存入栈顶，此时栈里从栈顶到栈底依次有30和5两个操作数。
- 继续扫描，遇到了操作符“+”，栈里距离其最近的两个操作数是30和4，所以进一步计算是4 + 30，得到34这个结果，暂时存入栈中。
- 继续扫描，后缀表达式已经扫描完毕，现在栈里只剩下一个操作数34，34就是我们要求的最后结果。
后缀表达式求值的算法流程
根据上面的例子，可以总结出后缀表达式求值的一般算法流程：
第一，创建空栈operandStack用于暂时存放操作数。
第二，将字符串形式的后缀表达式用split方法转化为单词token的列表。
第三，从左至右扫描单词token列表。
- 如果单词是一个操作数operand，将单词转换为int，压入operandStack栈顶。
- 如果单词是一个操作符operator（"*/+-"），就开始求值，从栈顶弹出2个操作数，先弹出的是右操作数，后弹出的是左操作数（这一点在计算"/"和"-"，即除法和减法时尤其要注意），计算后将值重新压入栈顶。
第四，单词列表扫描结束后，表达式的值就在栈顶。
第五，弹出栈顶的值，返回。
具体代码实现如下：
# 后缀表达式求值的程序。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def postfixEval(postfixExpr):
"""
postfixexpre：一个字符串类型的后缀表达式，操作数与操作符之间都有空格" "隔开。
如"AB*+C"是错误的输入，"A B * + C"才是正确的输入。
"""
operandStack = Stack()
tokenList = postfixExpr.split()
for token in tokenList:
if token in "0123456789": #操作数。
operandStack.push(int(token))
else: #操作符。
operand2 = operandStack.pop()
operand1 = operandStack.pop()
result = doMath(token, operand1, operand2)
operandStack.push(result)
return operandStack.pop()
def doMath(op, op1, op2):
if op == "*":
return op1 * op2
elif op == "/":
return op1 / op2
elif op == "+":
return op1 + op2
else:
return op1 - op2
print(postfixEval("4 5 6 * +"))
<<<34
To be continued.
