栈应用之 后缀表达式计算 （python 版）
后缀表达式特别适合计算机处理
1. 中缀表达式、前缀表达式、后缀表达式区别
中缀表达式：(3 - 5) * (6 + 17 * 4) / 3 17 * 4 + 6 前缀表达式：/ * - 3 5 + 6 * 17 4 3 * 17 4 + 6 后缀表达式：3 5 - 6 17 4 * + * 3 / 17 4 * 6 +
2. 算法核心
假定 st 是一个栈 （栈的特点：后进先出 LIFO）
比如 【3 / 5】 即 【3 5 / 】；
3 先压入栈，而后 5 出栈；
元素在栈里面的顺序应该是 【5，3】；
5 先出栈，而后 3 出栈。
所以第二个运算对象先出栈，第一个运算对象后出栈。
1 # 扩充栈的方法 计算栈元素个数 2 class ESStack(SStack): 3 """docstring for ESS""" 4 def depth(self): 5 return len(self._elems)
1 def auf_exp_evaluator(exp): 2 operatora = '+-*/' 3 st = ESStack() # 扩充功能的栈，可用depth()检查元素个数 4 5 for x in exp: 6 if x not in operatora: 7 st.push(flaot(x)) 8 continue # 跳过本次for循环 9 10 if st.depth() < 2 : 11 raise SyntaxError{"Short of operand(s)"} 12 a = st.pop() # 取出第二个运算对象 13 b = st.pop() # 取出第一个运算对象 14 15 if x == "+" ： 16 c = b + a 17 elif x == "-": 18 c = b - a 19 elif x == "*" ： 20 c = b * a 21 elif x == "/" : # 这里可能引发异常 ZeroDivisionError 22 c = b / a 23 else : 24 break # 这一步不可能出现，只是为了方便看、理解 25 26 st.push(c) # 将本次运算结果压入栈 27 28 if st.depth() == 1 # 如果栈里面只有一个元素，表示计算完成 29 return st.pop() 30 raise SyntaxError{"Extra operand(s) ."}