栈应用之 后缀表达式计算 （python 版）

栈应用之 后缀表达式计算 （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 出栈。

　　　　所以第二个运算对象先出栈，第一个运算对象后出栈。

 # 扩充栈的方法 计算栈元素个数

 class ESStack(SStack):

     """docstring for ESS"""

     def depth(self):

         return len(self._elems)

 def auf_exp_evaluator(exp):

     operatora = '+-*/'

     st = ESStack()             # 扩充功能的栈，可用depth()检查元素个数

     for x in exp:

         if x  not in operatora:

             st.push(flaot(x))

             continue            # 跳过本次for循环

         if st.depth() < 2 :

             raise SyntaxError{"Short of operand(s)"}

         a = st.pop()            # 取出第二个运算对象

         b = st.pop()            # 取出第一个运算对象

         if x == "+" ：

             c = b + a

         elif x == "-":

             c = b - a

         elif x == "*" ：

             c = b * a

         elif x == "/" :    # 这里可能引发异常 ZeroDivisionError

             c = b / a

         else :

             break          # 这一步不可能出现，只是为了方便看、理解

         st.push(c)         # 将本次运算结果压入栈

     if st.depth() == 1     # 如果栈里面只有一个元素，表示计算完成

         return st.pop()

     raise SyntaxError{"Extra operand(s) ."}