整理定义

前置知识：

树、二叉树

概念定义

算术表达式是由数字、运算符、括号以及代数变量等组成的式子，例如 (3 + 4) * 5。在计算机科学中，算术表达式通常用于描述数学公式和算法。

逆波兰表达式（Reverse Polish Notation，RPN），也叫后缀表达式，是一种去掉括号且依然能定义清楚优先级的算术表达式。例如，上述的算术表达式 (3 + 4) * 5 在逆波兰表达式中表示为 3 4 + 5 *。

波兰表达式：也称前缀表达式，是把运算符放在两个操作数之前的表达式方式。例如，上述的算术表达式 (3 + 4) * 5 在波兰表达式中表示为 * + 3 4 5。

中缀表达式：是把运算符放在两个操作数之间的表达式方式。例如，上述的算法表达式(3 + 4) * 5 就是中缀表达式。

应用场景

计算器：许多计算器，包括计算机的计算器程序，使用逆波兰表达式来处理算术表达式，因为这种方式可以消除括号，简化计算过程。
编译器：编译器在解析算术表达式时，通常会将其转换为逆波兰表达式，因为逆波兰表达式更容易转换为机器语言。

实例说明：

假设我们有一个算术表达式 (3 + 4) * 5，我们想要计算它的值。

首先，我们将这个算术表达式转换为逆波兰表达式，得到 3 4 + 5 *。
然后，我们从左到右读取逆波兰表达式，遇到数字就将其压入栈中，遇到运算符就从栈中弹出两个数字进行计算，然后将计算结果再压入栈中。
对于 3 4 + 5 *，我们首先将 3 和 4 压入栈中，然后遇到 +，所以我们从栈中弹出 4 和 3，计算 4 + 3 得到 7，然后将 7 压入栈中。
接着我们将 5 压入栈中，然

复述展开

二叉树的三种遍历方式

为什么要区分，前缀、后缀、中缀呢？这跟表达式中符号的所处的位置有关系。

我们先将表达式(3 + 4) * 5 使用二叉树表示出来。

根据遍历的不同顺序，我们可以分为前序遍历、中序遍历、后续遍历的方法，以上面的 3-4 表达式为例：

前序遍历：根节点，左子节点，右子节点【- 3 4】
中序遍历：左子节点，根节点，右子节点【3 - 4】
后续遍历：左子节点，右子节点，根节点【3 4 -】

可以发现，遍历的顺序与根节点的位置有关系，根节点的位置在前，就叫前序遍历；在后则是后续遍历；在中间则是中序遍历。

算术表达式

在了解了二叉树的三种遍历方式之后，就可以很自然地将表达式先转为二叉树，然后得出对应的前缀、后缀表达式了。

def infix_to_postfix(infix_expression):
    precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
    stack = []  # 用作栈的列表
    postfix = []  # 用来存储后缀表达式的列表
    for char in infix_expression:
        if char not in precedence:  # 如果是操作数，直接添加到后缀表达式
            postfix.append(char)
        else:
            while stack and precedence[char] <= precedence[stack[-1]]:  # 弹出所有优先级更高或相等的运算符
                postfix.append(stack.pop())
            stack.append(char)  # 将当前运算符压入栈
    while stack:  # 弹出栈中剩余的运算符
        postfix.append(stack.pop())
    return ' '.join(postfix)  # 返回后缀表达式

print(infix_to_postfix("3 + 4 * 5"))  # 输出 "3 4 5 * +"