python计算后续表达式

　　列举一个后续表达式：4 5 6 * +。当从左往右扫描该表达式时，首先会遇到操作数4和5.在遇

下一个符号之前，我们不确定要对它们进行计算。将他们都保存在栈中，变可以在需要是取用。

　　在本例中，紧接着出现的符号又是一个操作数。因此，将6也压入栈中，并继续检查后面的符

号。现在遇到运算符*。这意味着需要将最近遇到的两个操作数相乘。通过执行两次出栈操作，可

以得到相应的操作数，然后进行乘法运算，得到结果30。

　　接着，将结果压入栈中。这样一来当遇到后面的运算符时，它可以作为操作数。当处理完最

后一个运算符之后，栈中只剩一个值。将这个值取出来，并作为表达式的结果返回。

　　在列举一个复杂的例子：7 8 + 3 2 + /。有两处需要注意。首先伴随着子表达式的计算，栈增

大、缩小，然后再一次增大。其次，处理除去算法时需要非常小心。由于后续表达式只改变运算

符的位置，因此操作数的位置与在中序表达式中的位置相同。当从栈中去除除号的操作数时，它

们顺序颠倒了。由于除号不是可交换的运算符（15/5和5/15的结果不相同），因此必须保证操作

数的顺序没有颠倒。

　　假设后续表达式是一个以空格分隔的标记串，其中，运算符标记有*、/、+、-，操作数标记

的是一位的整数值。结果是一个整数。

　　（1）创建空栈operandStack。

　　（2）使用字符串方法split将输入的后续表达式转换成一个列表。

　　（3）从左往右扫描这个标记列表。

　　　　如果标记是操作数，将其转换成整数并且压入operandStack栈中。

　　　　若果标记是运算符，从operandStack栈中取出晾干操作数。第一次取出右操作数，第二次

取出左操作数。进行相应的算术运算，然后将运算结果压入operandStack栈中。

　　（4）当处理完输入表达式时，栈中的值就是结果。将其压入栈中返回。

 1 from pythonds.basic import Stack
 2 def postfixEval(postfixExpr):
 3     operandStack = Stack()
 4 
 5     tokenList = postfixExpr.split()
 6 
 7     for token in tokenList:
 8         if token in "0123456789":
 9             operandStack.push(int(token))
10         else:
11             operand2 = operandStack.pop()
12             operand1 = operandStack.pop()
13             result = doMath(token,operand1,operand2)
14             operandStack.push(result)
15 
16     return operandStack.pop()
17 
18 def doMath(op,op1,op2):
19     if op == "*":
20         return op1 * op2
21     elif op == "/":
22         return op1 / op2
23     elif op == "+":
24         return op1 + op2
25     else:
26         return op1 - op2