首页/新闻资讯/正文详情

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

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

相关推荐

间,最大化 CPU 利用率。 异步编程通过事件循环实现任务调度:当一个任务因 IO 操作需要等待时,事件循环会暂停该任务,切换到其他 ...
间,最大化 CPU 利用率。 异步编程通过事件循环实现任务调度:当一个任务因 IO 操作需要等待时,事件循环会暂停该任务,切换到其他 ...

异步编程:最大化 CPU 利用率的秘密武器 引言:为什么我们需要异步编程?想象一下,你正在一家繁忙的咖啡店排队点单。店员在等咖啡机煮咖啡时,如果只是呆呆站着等,那么后面的顾客就要等更久。但如果店员在等待… · 2026/9/21 8:59:24

CVE-2022-25845 FastJSON(com.alibaba:fastjson)
CVE-2022-25845 FastJSON(com.alibaba:fastjson)

springboot 升级以及漏洞处理 CVE-2022-25845 FastJSON(com.alibaba:fastjson)包引发的漏洞fastJson-1.2.68.jar com.alibaba.fastjson.parser.ParserConfig com.alibaba.fastjson.parser.deserializer.ThrowableDeserializer FastJSON 默认关闭 auto… · 2026/9/21 12:16:00

3步安装KK-HF Patch:解锁Koikatu/Koikatsu Party完整游戏体验的终极指南
3步安装KK-HF Patch:解锁Koikatu/Koikatsu Party完整游戏体验的终极指南

3步安装KK-HF Patch:解锁Koikatu/Koikatsu Party完整游戏体验的终极指南 【免费下载链接】KK-HF_Patch Automatically translate, uncensor and update Koikatu! and Koikatsu Party! 项目地址: https://gitcode.com/gh_mirrors/kk/KK-HF_Patch 还在为Koikat… · 2026/8/3 13:24:58

相城区北桥镇电工证到期换证流程:真实经历告诉你怎么避开坑
相城区北桥镇电工证到期换证流程:真实经历告诉你怎么避开坑

相城区北桥镇电工证到期换证流程:真实经历告诉你怎么避开坑 我初中毕业,干了十年电工,学历不高,但凭手艺在工地混得风生水起。去年电工证到期换证时,我差点被各种流程整懵,还好我早几年在郑州金水区当过工程类毕业生,那会儿也闹过不少笑话。今天我就用… · 2026/11/17 10:44:32

电务段需要高压电工证怎么报名 被中介坑了怎么破
电务段需要高压电工证怎么报名 被中介坑了怎么破

电务段需要高压电工证怎么报名 被中介坑了怎么破 你是不是也遇到过这种情况?手里拿着电务段的工作机会,却因为 高压电工证 没考下来而被卡住?或者你已经在电务段工作,但 怎么报名… · 2026/11/17 10:44:32

惠州高压电工证报名多久拿证?工地太忙根本没时间复习考试怎么办
惠州高压电工证报名多久拿证?工地太忙根本没时间复习考试怎么办

惠州高压电工证报名多久拿证?工地太忙根本没时间复习考试怎么办 工地太忙根本没时间复习考试,你是不是也这样?手上活儿干不完,还要抽空准备高压电工证的考试,时间根本不够用。别急,我这有真材实料的干货,教你 惠州高压电工证报名多久拿证… · 2026/11/17 10:44:32

宁德高压电工证报考如何突破学历限制?2026河南最新政策解读
宁德高压电工证报考如何突破学历限制?2026河南最新政策解读

宁德高压电工证报考如何突破学历限制?2026河南最新政策解读 你是不是也担心自己学历不高,怕报不上宁德高压电工证?别急,2026年河南最新政策已经明确,学历门槛正在逐步放宽。越来越多的行业从业者,尤其是那些在一线工作的电工师傅,开始意识到高… · 2026/11/17 10:44:32

来宾忻城县电工证年审怎么搞?官方报名入口在哪?别被中介骗了!
来宾忻城县电工证年审怎么搞?官方报名入口在哪?别被中介骗了!

来宾忻城县电工证年审怎么搞?官方报名入口在哪?别被中介骗了! 你是不是在来宾忻城县,正在为电工证年审发愁?担心不知道去哪报名,怕被中介骗钱,还怕搞错了流程?别急,这篇文章就给你讲明白,怎么在 来宾忻城县电工证年审 的流程里 避开坑 ,找到… · 2026/11/17 10:44:32

上城区电工证培训课题报名费多少钱,全国通用证书怎么拿更稳妥
上城区电工证培训课题报名费多少钱,全国通用证书怎么拿更稳妥

上城区电工证培训课题报名费多少钱,全国通用证书怎么拿更稳妥 实操考试心里没底怕挂科,你不是一个人。尤其是在上城区,越来越多的电工从业者开始关注【上城区电工证培训课题】,因为这不仅关系到能否上岗,更关乎未来的晋升与职业发展。但很多人对考试流程… · 2026/11/17 10:43:32

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/17 5:38:05

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/17 5:38:05

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/17 9:06:35

安徽特种工考证学校千万别踩坑,学历不高也能考证上岗
安徽特种工考证学校千万别踩坑,学历不高也能考证上岗

安徽特种工考证学校千万别踩坑,学历不高也能考证上岗 你是不是总觉得学历不高就考不了证,连报名资格都够不上?其实,很多人和你一样,学历不占优势,但想通过考证转行或提升自己的职业竞争力。安徽特种工考证学校虽然门槛不高,但千万别踩坑,稍有不慎就会… · 2026/11/17 0:00:20

你没学历也能考福田特种作业操作证?真实经历告诉你怎么干
你没学历也能考福田特种作业操作证?真实经历告诉你怎么干

你没学历也能考福田特种作业操作证?真实经历告诉你怎么干 你是不是觉得学历不高就考不上福田特种作业操作证?其实不然,我有个老乡,初中毕业,现在在安阳干焊工,每月拿8000多,还评上了高级技师。他的经历我今天就给你说说,看看你能不能照着走。… · 2026/11/17 0:00:20

低压电工证哪里盖章怎么报名 过期了别慌教你一步步复审
低压电工证哪里盖章怎么报名 过期了别慌教你一步步复审

低压电工证哪里盖章怎么报名 过期了别慌教你一步步复审 证书过期了不知道怎么复审延期?低压电工证是很多电工从业者必须持有的证件,一旦到期未及时办理复审,不仅影响工作,还可能面临被单位辞退甚至罚款。今天我就从南阳地区培训机构学员的角度,详细告诉… · 2026/11/17 0:00:20

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/16 16:48:43

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/16 16:48:57

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/16 16:48:48

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码