注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为9分钟。
接下来讨论通用的中缀表达式转换为后缀表达式的算法，以及如何使用Python程序来实现中缀表达式转换为后缀表达式这一过程。
通用的中缀转后缀表达式的算法思考
在后缀表达式中，操作符的出现顺序运算次序一致，因此会出现操作符调整顺序的情况。
中缀表达式转换为后缀表达式的处理过程中，操作符比操作数要晚输出。所以在程序扫描到对应的第二个操作数之前，需要先把操作符保存起来。
这些保存起来的操作符当中，由于优先级的规则，有的操作符可能需要反转次序输出。这种保存需求和反转特性，使得我们考虑用栈这种数据结构来保存暂时未处理的操作符。
比如A + B * C中，"+"虽然先出现，但是优先级不如后面的"*"，因此它要等到"*"操作符处理完成之后，才能再进行处理。
关于操作符的优先级，由于有括号强制优先级的情况，所以不一定是优先级更高的操作符排在前面，而是要看操作符实际的优先顺序。比如(A+B)*C中，“+”的优先级就要高于“*”，所以这个中缀表达式的后缀形式是AB+C*。对于这种情况，程序的算法又该如何解决呢？
解决方法是，程序扫描到左括号时，标记下来，其后出现的操作符的优先级要得到提高，当扫描到对应的右括号时，就可以马上输出这个优先级得到提高的操作符。
通用的中缀转后缀表达式的算法总结
想通了上述的各种细节，就可以对通用的中缀转后缀表达式的算法做一个总结了：
在从左到右逐个字符扫描中缀表达式的过程中，采用一个栈来暂存未处理的操作符。
由于栈的LIFO(后进先出)的特性，栈顶的操作符就是最近暂存进去的，当遇到一个新的操作符，就需要跟栈顶的操作符先比较优先级，再决定如何处理。
通用的中缀转后缀表达式的算法流程详解
注：后面的算法描述中，约定中缀表达式是由空格隔开的一系列单词(token，即最小的一个词法单位)构成。操作符的单词token包括*/+-()，操作数的单词token则是单字母标识符A、B、C等。
首先，创建空栈opstack用于暂存操作符，空列表postfixList用于保存后缀表达式。用字符串形式的中缀表达式转换为单词(token)作为元素构成的列表。
例如，"A + B * C"字符串利用字符串方法string.split(" ")转换成由操作数和操作符构成的列表['A', '+', 'B', '*', 'C']。
然后，再从左至右扫描中缀表达式单词列表，会有以下几种情况：
- 如果单词token是操作数，则直接添加到后缀表达式列表postfixList的末尾；
- 如果单词token是左括号“(”，则压入opstack栈顶（所谓压入栈顶，就是将元素入栈）；
- 如果单词token是右括号“)”，则反复弹出opstack栈顶操作符（所谓弹出栈顶，就是将元素移除出栈），加入到输出列表postfixList的末尾，直到碰到左括号为止；
- 如果单词是操作符“*/+-”，则压入opstack栈顶——压入之前，要比较其与opstack栈当前的栈顶操作符的优先级。如果当前栈顶的操作符的优先级高于或等于它，则要反复弹出栈顶的操作符，将栈顶的操作符输出并加入到列表postfixList的末尾，直到opstack栈顶的操作符的优先级低于它为止。把只装操作符的栈想象成一堆盘子，上面的是栈顶，下面的是栈底，这里的要求是，栈底的操作符的优先级必须小于栈顶的操作符。
接着，中缀表达式单词列表扫描结束后，把opstack栈中的所有剩余操作符依次弹出，添加到输出列表postfixList的末尾。
最后，把输出列表postfixList再用join方法使其转化为字符串形式的后缀表达式，算法结束。
具体实现的代码如下：
# 中缀表达式转后缀表达式的程序。
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 infixToPostfix(infixexpr):
"""
infixexpre：一个字符串类型的中缀表达式，操作数与操作符之间都由空格" "隔开。
如"A+B*C+D"是错误的输入，"A + B * C + D"才是正确的输入。
"""
# 下面连续6行是用一个字典记录操作符优先级。
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack() # 创建一个名为opStack的空栈。
postfixList = []
tokenList = infixexpr.split() # 解析表达式到单词列表。
for token in tokenList:
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789": #操作数。
postfixList.append(token)
elif token == '(': # 碰到左括号“(”，直接输出。
opStack.push(token)
elif token == ')': # 碰到右括号“)”，不停地弹出来。
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else: # 碰到操作符也是不停地弹出，直到栈顶的操作符优先级比自己低。
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop()) # 操作符。
return " ".join(postfixList) # 合成后缀表达式字符串。
print(infixToPostfix("A + B * C + D"))
<<<A B C * + D +
To be continued.
