企业官网建设流程全解析

聊聊前序、中序、后序表达式

在计算机科学和数学中，表达式的表示方式直接影响计算过程的复杂度和实现方式。我们日常使用的数学表达式，如3 + 5 * 2，被称为中序表达式（infix notation），因为运算符位于操作数之间。然而，这种表示方式对计算机并不友好，因为需要处理运算符优先级和括号。为了解决这个问题，诞生了前序表达式（prefix notation）和后序表达式（postfix notation），它们将运算符放在操作数之前或之后，从而消除了括号和优先级歧义。本文将从原理出发，深入剖析这三种表达式的特点、转换方法以及实际应用，并辅以可运行的代码片段。### 什么是前序、中序、后序表达式？这三种表达式都用于表示数学运算，区别在于运算符和操作数的排列顺序：-中序表达式：运算符位于操作数之间，例如A + B。这是人类最直观的写法，但需要括号和优先级规则来消除歧义，如(A + B) * C。-前序表达式：运算符位于操作数之前，例如+ A B。也称为波兰表示法（Polish Notation），由波兰逻辑学家 Jan Łukasiewicz 提出。它无需括号，因为运算顺序由位置决定。-后序表达式：运算符位于操作数之后，例如A B +。也称为逆波兰表示法（Reverse Polish Notation, RPN），是前序表达式的变体，广泛应用于栈式计算器（如 HP 计算器）和编译器中。为什么前序和后序表达式对计算机更友好？因为它们可以由一个简单的栈算法直接求值，无需处理括号和优先级。例如，表达式(3 + 5) * 2的中序形式需要明确括号，但前序形式* + 3 5 2和后序形式3 5 + 2 *则通过顺序计算即可。### 前序与后序表达式的求值原理求值前序和后序表达式的核心数据结构是栈。栈是一种后进先出（LIFO）的数据结构，非常适合处理嵌套的运算顺序。#### 后序表达式求值后序表达式的求值算法如下：1. 从左到右扫描表达式。2. 遇到操作数（数字），将其压入栈。3. 遇到运算符，从栈中弹出两个操作数（注意顺序：先弹出的是右操作数，后弹出的是左操作数），执行运算，结果压回栈。4. 扫描结束后，栈顶即为最终结果。#### 前序表达式求值前序表达式的求值算法相反：1. 从右到左扫描表达式。2. 遇到操作数，压入栈。3. 遇到运算符，从栈中弹出两个操作数（先弹出的是左操作数，后弹出的是右操作数），执行运算，结果压回栈。4. 扫描结束后，栈顶即为结果。为什么方向相反？因为前序表达式中，运算符位于操作数之前，从右向左扫描能先遇到操作数，从而正确匹配。### 代码示例1：后序表达式求值下面是一个用 Python 实现的后序表达式求值函数，支持加减乘除运算：pythondef evaluate_postfix(expression): """ 计算后序表达式的值。 参数 expression: 字符串，操作数和运算符以空格分隔，如 "3 5 + 2 *" 返回: 整数或浮点数结果 """ stack = [] # 将表达式分割为 token 列表 tokens = expression.split() for token in tokens: # 如果是操作数（数字），压入栈 if token.isdigit(): stack.append(int(token)) else: # 运算符：弹出两个操作数 # 注意：先弹出的是右操作数，后弹出的是左操作数 right = stack.pop() left = stack.pop() # 根据运算符执行计算 if token == '+': result = left + right elif token == '-': result = left - right elif token == '*': result = left * right elif token == '/': # 使用浮点除法，避免整数截断 result = left / right else: raise ValueError(f"未知运算符: {token}") # 将结果压回栈 stack.append(result) # 最终栈顶即为结果 return stack.pop()# 测试：计算 (3 + 5) * 2 的后序表达式postfix_expr = "3 5 + 2 *"print(f"后序表达式: {postfix_expr}")print(f"计算结果: {evaluate_postfix(postfix_expr)}") # 输出 16输出：后序表达式: 3 5 + 2 *计算结果: 16### 中序表达式转换为后序表达式在实际应用中，我们通常将中序表达式转换为后序表达式（或前序），再求值。转换算法由 Edsger Dijkstra 提出，称为调度场算法（Shunting-yard algorithm）。它使用一个操作符栈来调整运算符顺序，同时输出后序表达式。算法核心规则：- 从左到右扫描中序表达式。- 遇到操作数，直接输出到结果列表。- 遇到运算符，弹出栈中所有优先级不低于当前运算符的运算符，输出它们，然后将当前运算符压入栈。- 遇到左括号(，直接压入栈。- 遇到右括号)，弹出栈中运算符直到遇到左括号，并输出这些运算符，然后丢弃左括号。- 扫描结束后，弹出栈中剩余运算符并输出。### 代码示例2：中序转后序并求值下面是一个完整的程序，将中序表达式转换为后序表达式，然后求值：pythondef infix_to_postfix(expression): """ 将中序表达式转换为后序表达式。 参数 expression: 字符串，如 "3 + 5 * 2" 返回: 后序表达式字符串，如 "3 5 2 * +" """ # 定义运算符优先级 precedence = {'+': 1, '-': 1, '*': 2, '/': 2} output = [] # 存放后序表达式 token stack = [] # 操作符栈 # 分割表达式，假设操作数和运算符以空格分隔 tokens = expression.split() for token in tokens: # 如果是操作数（数字），直接输出 if token.isdigit(): output.append(token) elif token == '(': stack.append(token) elif token == ')': # 弹出直到左括号 while stack and stack[-1] != '(': output.append(stack.pop()) stack.pop() # 移除左括号 else: # 运算符：弹出优先级不低于当前运算符的运算符 while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(token, 0): output.append(stack.pop()) stack.append(token) # 弹出剩余运算符 while stack: output.append(stack.pop()) return ' '.join(output)# 测试转换infix_expr = "3 + 5 * 2" # 对应 (3 + (5 * 2))postfix_expr = infix_to_postfix(infix_expr)print(f"中序表达式: {infix_expr}")print(f"后序表达式: {postfix_expr}")# 使用之前定义的求值函数print(f"计算结果: {evaluate_postfix(postfix_expr)}") # 输出 13输出：中序表达式: 3 + 5 * 2后序表达式: 3 5 2 * +计算结果: 13### 深入原理：为什么前序和后序无需括号？中序表达式的歧义来源于运算符优先级和结合性。例如，3 + 5 * 2如果不加括号，按照数学规则是3 + (5 * 2) = 13，但若误解为(3 + 5) * 2 = 16则错误。前序和后序表达式通过位置固定了运算顺序。考虑前序表达式+ 3 * 5 2。从右向左扫描：遇到2和5压栈，遇到*弹出5和2得10，压栈；然后遇到3压栈，遇到+弹出3和10得13。这个顺序天然对应了3 + (5 * 2)，无需括号。后序表达式3 5 2 * +同理。从左向右扫描：3压栈，5压栈，2压栈，遇到*弹出5和2得10，压栈；遇到+弹出3和10得13。因此，前序和后序表达式本质上将运算顺序编码到了扫描方向或位置中，消除了对括号的依赖。### 总结前序、中序和后序表达式是表达式计算的三种核心表示法。中序表达式虽符合人类直觉，但需要复杂的解析；前序和后序表达式通过栈算法实现高效求值，广泛应用于编译器、计算器和科学计算中。本文通过原理剖析和可运行代码展示了后序表达式求值、中序转后序的调度场算法，并解释了为何前序和后序无需括号。理解这些概念，有助于深入掌握计算机语言解析和算法设计。无论你是学习数据结构还是开发编程语言，这三者都是不可或缺的基础。