什么是中序表达式

中序表达式就是我们日常使用的算术表达式，也称为中缀表达式。它的主要特点是操作符位于两个操作数之间，并且通常需要括号来改变运算的优先级

例如

3 + 4 × ( 5 + 6) - 8 / 2

什么是后序表达式

后序表达式，也被称为后缀表达式或逆波兰表示法（Reverse Polish notation，RPN），是一种算术表达式的书写方式，其中操作符位于其操作数之后。

例如

将 中序表达式 (1+4)×3+10/5 转后序表达式 1 4 + 3 * 10 5 / +

算法实现

class Stack:def __init__(self):self.items = []def isEmpty(self):return len(self.items) == 0def 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)

先定义好一个栈后续需要用到这个数据结构

import string
def infixToPostfix(infixexpr):prec = {}prec['*'] = 3prec["/"] = 3prec["+"] = 2prec["-"] = 2prec["("] = 1opStack = Stack()postfixList = []tokenList = infixexpr.split() # 切分空格for token in tokenList:if token in string.ascii_uppercase: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)

结果输出

infixToPostfix("( A + B ) * ( C + D )")'A B + C D + *'