前言
最近做面试题的时候碰到了前缀、中缀、后缀表达式的问题,题目如下:
表达式“X=A+B*(C-D)/E”的后缀表达式?
看到这里有点蒙,于是赶紧google,记录一下学习新得吧
概述
前缀表达式(Prefix Notation)是指将运算符写在前面操作数写在后面的不包含括号的表达式,而且为了纪念其发明者波兰数学家Jan Lukasiewicz,所以前缀表达式也叫做“波兰表达式”
后缀表达式(Postfix Notation)与之相反,是指运算符写在操作数后面的不包含括号的算术表达式,也叫做逆波兰表达式
中缀表达式(Infix Notation)就是常用的将操作符放在操作数中间的算术表达式。前缀表达式和后缀表达式相对于中缀表达式最大的不同就是去掉了表示运算符优先级的括号
与二叉树关系
前缀表达式对应于二叉树的前序遍历
中缀表达式对应于二叉树的中序遍历
后缀表达式对应于二叉树的后序遍历
根据中缀表达式生成二叉树
腾讯笔试题目:表达式“X=A+B*(C-D)/E”的后缀表示形式可以为?
按照操作符的优先级,其二叉树的生成过程:
1.括号的优先级最高,根为-,左孩子为C,右孩子为D
2.接下来是乘法,根为*,左孩子为B,右孩子为1的树
3.接下来是除法,跟为/,左孩子为2的树,右孩子为E
4.接下来是加法,根为+,左孩子为A,右孩子为3的树
5.接下来是=号,左孩子是X,右孩子是4的树
剩下的就是前序和后序遍历二叉树即可,代码都会写,还在乎遍历吗
因为,后序遍历序列是: XABCD-*E/+=
分享到:
相关推荐
用二叉树实现中缀表达式转换成后缀表达式,内含一个CPP文件的代码和一个截图,很不错的,是我自己写的。
前缀、中缀、后缀表达式[参照].pdf
表达式2*(9+6/3-5)+4,称为中缀表达式,表示成2 9 6 3 / + 5 - * 4 +称为后缀表达式,表示成+ * 2 - + 9 / 6 3 5 4称为前缀表达式。 ·基本要求 将中缀表达式,转换为后缀表达式和前缀表达式,再分别计算转换后的...
与前缀表达式(例:+ 3 4)或后缀表达式(例:3 4 +)相比,中缀表达式不容易被计算机解析,但仍被许多程序语言使用,因为它符合人们的普遍用法。 与前缀或后缀记法不同的是,中缀记法中括号是必需的。计算过程中...
不错 中缀表达式转后缀表达式 简单表达式运算
转
输入中缀表达式 输出后缀表达式树 VC6.0
前缀转换后缀中缀表达式 前缀转换后缀中缀表达式
中缀表达式就是我们通常所书写的数学表达式,后缀表达式也称为逆波兰表达式,在编译程序对我们书写的程序中的表达式进行语法检查时,往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的...
利用STL中stack,解析前、后缀表达式,并将中缀表达式转换到相应的前、后缀表达式。
文章目录前缀表达式(波兰表达式)前缀表达式分析与介绍思路分析中缀表达式中缀表达式分析与介绍后缀表达式(逆波兰表达式)后缀表达式分析与介绍思路分析逆波兰计算器代码实现逆波兰计算器中缀表达式转换为后缀...
该程序实现了运算表达式转换为中缀表达式、中缀表达式转换为后缀表达式及后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
利用二叉树的遍历来转换前缀表达式中缀表达式和后缀表达式
将一个表达式转为后缀表达式,用堆栈计算 中缀转后缀的过程中遇到数字直接输出,遇到符号则判断优先级。
中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
前缀、中缀、后缀表达式相互转换工具 你需要选择你输入的值是什么表达式类型,本来我是想要写一个自动检测输入的表达式是属于哪一种,但是奈何能力有限,搞了大半天都没搞出来,立即推,果断放弃,转换思路,让你...
数据结构课上的作业,完全实现题设要求,简单易懂
后缀表达式 (Postfix Notation),比如前所述的中缀表达式转换为后缀表达式为:"A B C * - D +"。 四、实例 中缀:a+b*c-(d+e) 后缀:((a(bc)* )+ (de)+ )- 把括号去掉:abc*+de+- 前缀:-( +(a *(bc)) +(de)) 把...
3、要求在语法分析模块中利用语法制导翻译技术完成具体的中缀表达式到后缀表达式的翻译,其中包括按前述翻译器的规格说明构建对应表达式、项、因子的非终结符expr、term和factor的函数以及检查记号是否匹配的函数;...
把一个原表达式分别转化前缀 中缀 后缀,并分别求值