APP
最详细的中缀转后缀
学渣们请就座：（不用看别人，说的就是你！）
大家好，我是Dream。此时此刻我只想说：男神可以迟到，但永远不会缺席！那个男人回来了！！！
最近眼发炎了，非常难受，但这不会阻止我为大家更新文章的，请把 泪目 打在评论区！！！
话不多说，今天给大家介绍一下，中缀表达式如何转后缀表达式。
现在，肯定会有学渣问：什么是中缀和后缀表达式呢？
我只想说：你好优秀，请前排就坐~
简单来讲，中缀表达式就是我们学习数学时的各种表达式，
such as：（A+B）*C/(D-E)
什么是后缀表达式呢？就是将运算符移动到字符串后面，但也不是全部移动到后面，当然也是有条件和顺序的。
我们都知道运算符是有优先级的，比如乘号的优先级就高于加号的优先级，那就要在同一运算区域下先移动乘号再移动加号，为什莫说在同一领域下呢，因为我们都知道在运算中少不了括号的存在，那么括号就界定了属不属于同一领域下。
算了，不和你们多BB了，举个例子吧：
A+B : AB+
A+B *C : ABC *+
(A+B) *(C+D) : AB+CD+ *
emmm,我猜你还是不懂应该（仅代表学渣）
好吧，前两个你应该懂了吧（不懂的同学回家默写三千遍三字经）
那我来讲一下第三个：首先(A+B) *(C+D)可以写作（(A+B) *(C+D)）没有问题吧，先看第一层括号，第一层括号中只有两个小括号和一个 *，那么好的将最外层右边的括号用乘号替换掉，左边括号删除，即：(A+B) (C+D) *
同理看第二层括号，同样方法，运算符替换掉右边括号，同时删除左边括号，即：AB +(C+D) *----AB +CD+ *得到了最终答案， 是不是very easy？那你会用代码表示吗？？？哈哈哈，继续！
首先调用栈和string：
from pythonds3.basic import Stack
import string
定义一个函数：
def infix_to_postfix(infix):
"""将中序表达式转化为后序表达式，核心思想"""
这里定义了一个栈来储存运算符，一个列表来储存得到的表达式。
最后将得到的列表用join函数合并成一个字符串
当出现括号左时入栈，字符串照常输出在列表中，运算符继续入栈，当出现有括号时运算符出栈，直至遇到最初的左括号才停止出栈！就这样循环往复遍历，直至遍历结束。
in_list = infix.split() # 将字符串变为列表，注意，输入时需要空格隔开单个元素，例："1 2 3 * 2 3"
stack1 = Stack() # 创建空栈，用于存储遍历字符串列表的括号、操作符
post_list = [] # 创建空列表，用于存储后序表达式
priority = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1} # 创建优先级字典
for elem in in_list: # 遍历中序表达式
if elem == '(': # 为左括号，入栈
stack1.push(elem)
elif elem in string.ascii_uppercase: # 为字符串里的大写字母，加入空的输出列表
post_list.append(elem)
elif elem == ')': # 为右括号，则出栈，添加到输出列表，直到匹配到左括号
token = stack1.pop()
while token != '(':
post_list.append(token)
token = stack1.pop()
else: # 为操作符，则判断栈中是否有更高优先级的操作符，有则出栈，无则添加到列表尾部，
while (not stack1.is_empty()) and (priority[stack1.peek()] >= priority[elem]):
post_list.append(stack1.pop())
stack1.push(elem) # 若放到列表尾部，则栈永远不会有操作符
while not stack1.is_empty(): # 若栈不为空，则弹出到后续表达式列表（即优先级低的放最后）
post_list.append(stack1.pop())
return ''.join(post_list) # 将列表连在一起
if __name__ == '__main__':
print(infix_to_postfix("A * B + ( C + D ) * ( E - F )"))
emmm，这就是今天我和大家分享的东西了。
如果你喜欢的话，就不要吝惜你的一键三连了~
本文摘自 ：https://blog.51cto.com/u
