聊聊前序、中序、后序表达式在计算机科学和数学中表达式的表示方式直接影响计算过程的复杂度和实现方式。我们日常使用的数学表达式如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。因此前序和后序表达式本质上将运算顺序编码到了扫描方向或位置中消除了对括号的依赖。### 总结前序、中序和后序表达式是表达式计算的三种核心表示法。中序表达式虽符合人类直觉但需要复杂的解析前序和后序表达式通过栈算法实现高效求值广泛应用于编译器、计算器和科学计算中。本文通过原理剖析和可运行代码展示了后序表达式求值、中序转后序的调度场算法并解释了为何前序和后序无需括号。理解这些概念有助于深入掌握计算机语言解析和算法设计。无论你是学习数据结构还是开发编程语言这三者都是不可或缺的基础。
聊聊前序、中序、后序表达式
聊聊前序、中序、后序表达式在计算机科学和数学中表达式的表示方式直接影响计算过程的复杂度和实现方式。我们日常使用的数学表达式如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。因此前序和后序表达式本质上将运算顺序编码到了扫描方向或位置中消除了对括号的依赖。### 总结前序、中序和后序表达式是表达式计算的三种核心表示法。中序表达式虽符合人类直觉但需要复杂的解析前序和后序表达式通过栈算法实现高效求值广泛应用于编译器、计算器和科学计算中。本文通过原理剖析和可运行代码展示了后序表达式求值、中序转后序的调度场算法并解释了为何前序和后序无需括号。理解这些概念有助于深入掌握计算机语言解析和算法设计。无论你是学习数据结构还是开发编程语言这三者都是不可或缺的基础。
